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
$$B \begin{pmatrix}1\\x\\x^2\\x^3\\ \vdots\end{pmatrix} = n$$
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.

 

[CellCoree]

I would approach this problem by first understanding the concept of unique powers. Unique powers refer to the exponent values in an expression that are not repeated. In other words, the powers must be distinct integers.

In the given example, the number 35 is not a perfect power, meaning it cannot be written as an integer raised to a power. Therefore, it cannot be written as a sum of unique powers of a number.

To further illustrate, let's take the number 13. As mentioned, it can be written as 30 + 31 + 32 = 15. This is because 3 is the base and the powers are unique (0, 1, and 2). However, if we try to write 13 as a sum of unique powers of a different number, say 2, we would get 20 + 21 + 22 = 14, which is not equal to 13. This shows that the number 13 can only be written as a sum of unique powers of 3 and not any other number.

In general, for any given number, we can determine if it can be written as a sum of unique powers of a number by first finding its prime factorization. If the prime factors are not all the same, then the number cannot be written as a sum of unique powers. However, if the prime factors are all the same, then it may be possible to write the number as a sum of unique powers.

In conclusion, the number 35 cannot be written as a sum of unique powers of a number, while the number 13 can only be written as a sum of unique powers of 3. This approach can be applied to any given number to determine if it can be written as a sum of unique powers of a number.