# Sum of consecutive nth powers

Given a positive integer $$\n\$$, output all integers $$\b\$$ (such that $$\1) where $$\n\$$ can be written as the sum of any number of consecutive powers of $$\b\$$.

Example:

Let's say $$\n=39\$$.

$$\3^1+3^2+3^3\$$
$$\= 3 + 9 + 27\$$
$$\= 39\$$

This does not work for any other $$\b\$$, so our output is .

Test cases up to $$\n=50\$$:

1: []
2: []
3: []
4: 
5: []
6: 
7: 
8: 
9: 
10: []
11: []
12: [2,3]
13: 
14: 
15: 
16: [2,4]
17: []
18: []
19: []
20: 
21: 
22: []
23: []
24: 
25: 
26: []
27: 
28: 
29: []
30: [2,5]
31: [2,5]
32: 
33: []
34: []
35: []
36: [3,6]
37: []
38: []
39: 
40: 
41: []
42: 
43: 
44: []
45: []
46: []
47: []
48: 
49: 
50: []


Clarifications:

• Is 1+2+4 supposed to be allowed for 7, given that 1+6 is not?
– Neil
Sep 5 at 8:17
• @Neil it says $1<b<n-1$. For $n=7$, 6 is not less than n-1.
– MTN
Sep 5 at 8:19
• Note that it’s recommended to leave your challenge in the Sandbox for at least 72 hours. However, it is still a good challenge. Sep 5 at 9:10

# JavaScript (V8), 62 bytes

Prints the results.

n=>{for(b=1;i=++b<n-1;k||print(b))for(k=n;k%b?i--:k/=b;)k-=!i}


Try it online!

### Algorithm

Given the input $$\n\$$ and for each $$\b\in[2,n-2]\$$:

1. we do $$\n\gets n/b\$$ as long as $$\n\equiv 0\pmod b\$$
2. we do $$\n\gets (n-1)/b\$$ as long as $$\n-1\equiv 0\pmod b\$$

If we end up with $$\n=0\$$, then $$\b\$$ is a solution.

### Explanation

If $$\n\$$ is of the form $$\b^p+b^{p+1}+\dots+b^{p+q}\$$, the first step will normalize it to:

$$b^0+b^1+\dots+b^q$$

and each iteration of the second step will remove the most significant term ...

$$b^0+b^1+\dots+b^{q-1}$$

... until it's eventually reduced to $$\0\$$.

### C (gcc), 79 bytes

Essentially the same code.

b,i,k;f(n){for(b=1;i=++b<n-1;k||printf("%d ",b))for(k=n;k%b?i--:(k/=b);)k-=!i;}


Try it online!

I wish it could be rearranged to get rid of :(k/=b). The obvious way is k%b<1?k/=b:i--, but that's just as long.

# Vyxal, 73 bitsv2, 9.125 bytes

⇩Ḣ'?ʀeÞSṠ?c


Try it Online!

Formulas? No we do things brute force around here.

## Explained

⇩Ḣ'?ʀeÞSṠ?c­⁡​‎‎⁪⁡⁪⁠⁪⁡⁪‏⁠‎⁪⁡⁪⁠⁪⁢⁪‏⁠‎⁪⁡⁪⁠⁪⁣⁪‏‏​⁡⁠⁡‌⁢​‎‎⁪⁡⁪⁠⁪⁢⁣⁪‏⁠‎⁪⁡⁪⁠⁪⁢⁤⁪‏⁠‎⁪⁡⁪⁠⁪⁣⁡⁪‏‏​⁡⁠⁡‌⁣​‎‎⁪⁡⁪⁠⁪⁤⁪‏⁠‎⁪⁡⁪⁠⁪⁢⁡⁪‏⁠‎⁪⁡⁪⁠⁪⁢⁢⁪‏‏​⁡⁠⁡‌⁤​‎‎⁪⁡⁪⁠⁪⁣⁢⁪‏⁠‎⁪⁡⁪⁠⁪⁣⁣⁪‏‏​⁡⁠⁡‌­
⇩Ḣ'          # ‎⁡Keep all from the range [2, n - 2] where:
ÞSṠ    # ‎⁢  Sums of sublists of
?ʀe       # ‎⁣  The number raised to each number in the range [0, input]
?c  # ‎⁤  Contains the input
💎


Created with the help of Luminespire.

# Charcoal, 24 20 bytes

ＮθＩΦ…²⊖θ¬⊙⪪⍘θι0⁻λＩ¬μ


Try it online! Link is to verbose version of code. Explanation: When converted to base b, n has to have the form 1+0*, thus when split on 0 the first part can only contain 1s and the other parts must be empty, although the code "permits" 0s.

Ｎθ                      Input n as a number
…                   Range from
²                  Literal integer 2 to
θ                Input n
⊖                 Decremented
Φ                    Filtered where
θ           Input n
⍘            Converted to base
ι          Current value
⪪             Split on
0         Literal string 0
¬⊙              All parts satisfy
λ       Current part
⁻        Only contains occurrences of
μ    Inner index
¬     Logical Not
Ｉ      Cast to string
Implicitly print

• Nice observation!
– MTN
Sep 5 at 9:23

# Jelly, 10 bytes

½Ḋbt0ỊƑɗ@Ƈ


A monadic Link that accepts a positive integer and yields a list of all valid integer bases.

Try it online!

### How?

A base, $$\b\$$, works for $$\n\$$ when $$\n\$$ converted to base $$\b\$$ is a run of ones optionally followed by a run of zeros.

No $$\b > \sqrt{n}\$$ can work since the $$\b^2\$$ term breaks the bank on its own and the $$\b^1\$$ and $$\b^0+b^1\$$ solutions are the excluded cases $$\b\ge n-1\$$.

½Ḋbt0ỊƑɗ@Ƈ - Link: positive integer, n
½          - square-root {n}
Ḋ         - dequeue -> B = [2,3,4,...,floor(sqrt(n))]
Ƈ - keep those {b in B} for which:
ɗ@  -   last three links as a dyad with swapped arguments - f(n, b):
b        -     convert {n} to base {b}
t0      -     trim zeros (e.g. [4,0,1,0,0,0] -> [4,0,1])
Ƒ    -     is invariant under?:
Ị     -       insignificant? (abs(digit)<=1 vectorised)


# Python, 82 bytes

-1 byte, thanks to xnor
-1 byte, thanks to Arnauld

lambda n:[b for b in range(2,n-1)for i in range(n*n)if~-b*n==b**(i%n+1)-b**(i//n)]


Attempt This Online!

Uses the equation $$\\sum_{k=i}^{j}b^k = \frac{b^{j+1}-b^i}{b-1}\$$

• It looks like you can save a byte writing b**(i%n+1)-b**(i//n)==n*~-b
– xnor
Sep 5 at 18:42
• You can save another byte by doing if~-b*n==... Sep 7 at 22:37

f n|r<-[0..n]=[i|i<-[2..n-2],a<-r,b<-r,n*i-n==i^a-i^b]


Try it online!

# Ruby, 55 56 bytes

->n{(2..n-2).select{|x|/^[0_]*(1_)+1$/=~n.digits(x)*?_}}  Try it online! If a number n is the sum of consecutive powers of x, then its representation is base x is a sequence of 1s followed by any number of zeroes. • Why are you joining by '_'? Won't joining by the empty string '' and checking /^0*1+$/ be sufficient? 49 bytes after also fixing the bug ovs brought up Sep 6 at 1:12
• @ValueInk it does not work for bases >= 12, because a single digit can be 11. For example f is [3, 16]
– G B
Sep 6 at 6:22

# K (ngn/k), 28 26 bytes

{2+&x{i~!#i:&y\x}'-1_2_!x}


-2 thanks to @coltim

Try it online!

• You can trim a couple bytes by using an "infix" {...}', i.e. x{i~!#i:&y\x}'-1_2_!x Oct 26 at 22:25

0#i=[]
n#i=mod n i:div n i#i
f n=[i|i<-[2..n-2],all(==1)$snd$span(<1)$n#i]  Attempt This Online! # 05AB1E, 12 11 bytes tL¦ʒIÝmŒOIå  -1 byte thanks to @MTN by porting tL¦ from @JonathanAllan's Jelly answer. Explanation: t # Get the square-root of the (implicit) input-integer L # Pop and push a list in the range [1,floor(sqrt(input))] ¦ # Remove the leading 1 to make the range [2,floor(sqrt(input))] ʒ # Filter this list by: IÝ # Push a list in the range [0,input] m # Take the current integer to the power of each of these values Œ # Get all sublists of this list O # Sum each inner sublist Iå # Check whether the input is in this list of sums # (after which the filtered list is output implicitly as result)  • 11 bytes (see Jonathan Allan's Jelly answer) – MTN Sep 8 at 14:53 # Wolfram Language (Mathematica), 58 bytes Select[r=Range[0,#-2],Tr/@Subsequences[#^r]&/*MemberQ[#]]&  Try it online! -2 bytes from @att • 58 bytes – att Sep 9 at 19:44 # Nekomata, 9 bytes ←ᶠ{ᵈqEů∑=  Attempt This Online! ←ᶠ{ᵈqEů∑= ← Decrement ᶠ{ Filter the range [0, n) by: ᵈq Find any subsequence of the range [0, input) E Power ů Check that it does not contain duplicates so that the base is not 1 ∑ Sum = Check that it is equal to the input  # Nekomata, 10 bytes ←ᶠ{1>B:o±=  Attempt This Online! A port of @Jonathan Allan's Jelly answer. ←ᶠ{1>B:o±= ← Decrement ᶠ{ Filter the range [0, n) by: 1> Check that it is greater than 1 B Convert the input to that base : = Check that it is invariant under: o Sort ± Sign  Now I regret supporting converting to base 1, otherwise that 1> could be omitted. # Perl 5, 88 bytes sub{grep{$x=$_;join('+',map$x**$_,0..$n)=~/\b.+\b(??{$n-eval$&?$;:""})/}2..sqrt($n=pop)}


Try it online!

# Scala 3, 85 bytes

n=>for{b<-2 to n-2;i<-0 to n*n-1;if(b-1)*n==math.pow(b,i%n+1)-math.pow(b,i/n)}yield b


Attempt This Online!

Uses the equation $$\\sum\limits_{k=i}^{j}b^k = \frac{b^{j+1}-b^i}{b-1}\$$