3
$\begingroup$

I have a list of numbers and I want to express each one as an integer linear combination of $2^{(2^k)}$ powers.

Some elements of the list are

(3748, 64594, 16700300, 68685479824, 4722365919717929558384, ...)

The first two elements can be expressed for example as

$$ 3748 = 2^2 - 6\cdot2^4 + 15\cdot2^8 $$

and

$$ 16700300= - 2^2 + 9\cdot2^4 - 45\cdot2^8 + 255\cdot2^{16}, $$

where the exponents $2$, $4$, $8$ and $16$ are all powers of 2.

Can you help me write a program which yields such coefficients? the answers must be of the form ...+-+-+-...

3748 ===> {1, -6, 15}

16700300 ===> {-1, 9, -45, 255}

I also realised that if the prime factors of the number are not raised to any power then you can find the coefficients here (i.e. 2*3*5*7 has n=4)

  n= number of distinct primes
 Table[(-1)^(n - k) Binomial[n, k], {k, 0, n}]

Is there a formula for factors raised to powers?

$\endgroup$
  • $\begingroup$ @Szabolcs now I know I misinterpreted the question. $\endgroup$ – Kuba Feb 24 '17 at 11:08
  • $\begingroup$ Possibly useful: mathworld.wolfram.com/IntegerRelation.html $\endgroup$ – Szabolcs Feb 24 '17 at 11:10
  • 3
    $\begingroup$ So you want coefficients with alternating signs? That makes a pretty big difference. Why did you not spell that out clearly when you first asked the question? This is a good example of how badly stated questions (and then the inevitable major changes to them) lead to wasted time for everyone. $\endgroup$ – Szabolcs Feb 24 '17 at 13:19
  • $\begingroup$ The decompositions seem not to be unique unless you impose further constraints on the coefficients. For instance, I could also write 3748 ===> {17, -6, 14}. Do you have additional constraints that make the decomposition unique? $\endgroup$ – user46676 Feb 24 '17 at 13:40
2
$\begingroup$

Some numbers might not be representable, as for example, 1. And, what do you want to do if the solution is not unique? You can use this simple program

given = 3748;
(*Find upper bound*)
upn = 0;
While[
  given > 2^2^upn, upn++
  ];
upn;
Print["Upper bound: ", upn]
(*Build series*)
cs = Array[c, upn + 1];
ser = Sum[cs[[k + 1]]*2^2^k, {k, 0, upn}]
(*Solve*)
sol = Solve[given == ser, cs, Integers]
(*Find one example*)
fi = FindInstance[given == ser, cs, Integers]
(*Check*)
given == ser /. fi[[1]]
csalt = {c[1] -> 0, c[2] -> 1, c[3] -> -6, c[4] -> 15, c[5] -> 0};
given == ser /. csalt

enter image description here

First, I determine an upper bound for $2^{(2^k)}$, so I can then build up a series up to that upper bound. With Solve you can search for integer solutions, but these will not be unique. After Solve I looked for one solution with FindInstance. As you can see, I found a solution fi different from yours csalt which is also able to represent the given number.


For your numbers you can run the following lines

nums = {3748, 64594, 16700300, 68685479824, 4722365919717929558384};
Do[
 given = nums[[i]];
 upn = 0;
 While[Abs[given] > 2^2^upn, upn++];
 cs = Array[c, upn + 1];
 ser = Sum[cs[[k + 1]]*2^2^k, {k, 0, upn}];
 fi = FindInstance[given == ser, cs, Integers];
 Print[given];
 out = Table[{k, cs[[k + 1]]}, {k, 0, upn}] /. fi[[1]];
 Print[out]
 , {i, 1, Length@nums}
 ]

enter image description here

The output lists $\{\{k_1,c_1\},\{k_2,c_2\},....\}$ give you the information of the found coefficients $c$ for the corresponding exponents $k$ for the series $\sum_{k=0}^n c_k 2^{(2^{k})}$.

$\endgroup$
  • $\begingroup$ Thank you very much for your effort.I believe that you answered my questions.Unfortunately (now that I'm looking your results) I think that I need answers of the form +-+-+-+. I realised that when the number has simple factors(not raised in powers) like 2*3*5*7 then the answer is Table[(-1)^(n - k) Binomial[n, k] 2^(2^k), {k, 0, n}]. Is there a way to find such formula for "more composite integers" like 2*2*3*5? Thanks $\endgroup$ – J42161217 Feb 24 '17 at 12:40
  • $\begingroup$ Then it would be helpful if you would edit your question, such that it is specific and clear for everybody. $\endgroup$ – Mauricio Fernández Feb 24 '17 at 12:49
  • $\begingroup$ ok. I will. In the Table that i send you, n=number of distinct factors $\endgroup$ – J42161217 Feb 24 '17 at 12:52
2
$\begingroup$

The question was changed, rendering the below answer irrelevant. I will not delete it though, as it may be of interest to someone else.


Take a look at Integer Relations and Lattice Reduction on MathWorld, as well as the first example under Applications in LatticeReduce.

Given integers $x_i, i=1..k$, it shows how to find integer coefficients $a_i$ so that

$$a_1 x_1 + a_2 x_2 + \cdots + a_k x_k = 0$$

Following the same method, we can attempt to find such relations by choosing $x_1$ as the number to be decomposed, and $x_2, x_3, \dots$ as the desired powers of $2$. However, this method is not guaranteed to find such a decomposition even if one does exist.

num = 68685479824; (* number to decompose *)
n = 5; (* how many powers to take into account *)
a = Transpose@Append[IdentityMatrix[n + 1],
      Prepend[2^(2^Range[n]), num]
    ];

In the result returned by LatticeReduce, we are looking for vectors which end in 0 (which means that the integer relation is satisfied) and that start in 1 or -1 (which means that num appears with a coefficient of 1, i.e. $a_1 = \pm 1$).

Cases[LatticeReduce[a], {1 | -1, ___, 0}]

(* {{1, -4, -8, -63, 519, -16, 0}} *)

Thus one possible solution for 68685479824 is {4, 8, 63, -519, 16}


Going through your list of numbers, I found the following possible solutions:

3748                     {-3, -5, 15}
64594                    ?
16700300                 {-1, -7, -44, 255}
68685479824              {4, 8, 63, -519, 16}
4722365919717929558384   {-4, -8, -94, 1545, -131119, 256}
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.