1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Sum of unique powers of a number

  1. Jul 22, 2010 #1
    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.
     
  2. jcsd
  3. Jul 22, 2010 #2

    Office_Shredder

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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
     
  4. Jul 22, 2010 #3
    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
     
  5. Jul 23, 2010 #4

    disregardthat

    User Avatar
    Science Advisor

    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.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook