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

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?

• @Szabolcs now I know I misinterpreted the question. – Kuba Feb 24 '17 at 11:08
• Possibly useful: mathworld.wolfram.com/IntegerRelation.html – Szabolcs Feb 24 '17 at 11:10
• 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. – Szabolcs Feb 24 '17 at 13:19
• 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? – user46676 Feb 24 '17 at 13:40

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[]
csalt = {c -> 0, c -> 1, c -> -6, c -> 15, c -> 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[];
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})}$.

• 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 – J42161217 Feb 24 '17 at 12:40
• Then it would be helpful if you would edit your question, such that it is specific and clear for everybody. – Mauricio Fernández Feb 24 '17 at 12:49
• ok. I will. In the Table that i send you, n=number of distinct factors – J42161217 Feb 24 '17 at 12:52

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}