Sum of unique powers of a number

  • Thread starter ged25
  • Start date
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 :
30 + 31 + 32 = 15

I hope my question is clear.
 

Office_Shredder

Staff Emeritus
Science Advisor
Gold Member
3,734
98
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 30 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
 
Your problem can be written as follows
[tex]
B \begin{pmatrix}1\\x\\x^2\\x^3\\ \vdots\end{pmatrix} = n
[/tex]
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

Science Advisor
1,844
33
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.
 

Physics Forums Values

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving

Hot Threads

Top