Expressing numbers as the sum of 2^(2^k) powers

Question

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?

Answer 1

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

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}
 ]

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})}$.

Answer 2

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}