Sum of unique powers of a number

[ged25]

Suppose you are given a number 35, how can you say if the number can be written as the sum of unique powers of a number ?

For example, 11 cannot be written as a sum of powers of number 3.
But 13 can be written as follows :
3⁰ + 3¹ + 3² = 15

I hope my question is clear.

 

[Office_Shredder]

You're basically asking given a number, in base k does it only have 1's and 0's? Just checking seems to be easy enough unless you're dealing with some huge numbers.

The algorithmic way to do this (say you want to see if n is written as powers of k)

Find the largest power of k that is smaller than n.

Divide n by that power of k and calculate the remainder.

The first digit of your base k representation is going to be the number you get out of the division. If that's not 1, you might as well stop now. If it is 1, you repeat the above on the remainder to get the next digit, and so on.

So to get 13, first we find the largest power of 3 smaller than it is 9. 13-1*9=4 so the first digit is a 1, and the remainder is a 4. The largest power of 3 that goes into 4 is 3, and 4-3*1=1 so the next digit is a 1 and the remainder is 1, which is 3⁰ so in base 3, 13 is 111.

For 35 on the other hand, 27 is the largest power and goes into 35 once with a remainder of 8. So the first digit is a 2. 9 does not go into 8 so the next digit is a 0. 3 goes into 8 twice with a remainder of 2 so the digit after that is a 2, and 1 goes into 2 twice so the last digit is a 2. So 35 is 1022 in base 3 so does not satisfy your criterion

 

[trambolin]

Your problem can be written as follows
<br /> B \begin{pmatrix}1\\x\\x^2\\x^3\\ \vdots\end{pmatrix} = n<br />
where B is a row vector with only 0 and 1 entries. Hence you might call it a binary integer programming problem.

Check out the page section integer unknowns on this page
http://en.wikipedia.org/wiki/Linear_programming

 

[disregardthat]

If you're making a program to calculate it for large numbers, you could shorten the process by making the following observation:

(k^n-1)/(k-1)=N
k^n=N(k-1)+1
so
N = 1 mod k

So you really only have to check for those k less than N such that N = 1 mod k.