Sum of consecutive nth powers

Question

Given a positive integer \$n\$, output all integers \$b\$ (such that \$1<b<n-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 [3].

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

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

Clarifications:

You can use this Python script to generate your own test cases.
This is code-golf, so shortest answer wins!

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. — The Empty String Photographer, Sep 5 at 9:10

Arnauld · Accepted Answer · 2023-09-08 11:13:54Z

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]\$:

we do \$n\gets n/b\$ as long as \$n\equiv 0\pmod b\$
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.

lyxal · Accepted Answer · 2023-09-05 09:12:05Z

Vyxal, 73 bits^v2, 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.

Neil · Accepted Answer · 2023-09-05 09:36:01Z

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

\$\begingroup\$ Nice observation! \$\endgroup\$
– MTN
Sep 5 at 9:23 — MTN, Sep 5 at 9:23

Jonathan Allan · Accepted Answer · 2023-09-05 22:52:04Z

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)

bsoelch · Accepted Answer · 2023-09-08 08:40:59Z

7

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}\$

edited Sep 8 at 8:40

answered Sep 5 at 8:43

bsoelch

5,7471 gold badge6 silver badges60 bronze badges

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

Add a comment |

xnor · Accepted Answer · 2023-09-05 18:47:44Z

5

Haskell, 54 bytes

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

Try it online!

answered Sep 5 at 18:47

xnor

144k26 gold badges273 silver badges637 bronze badges

Add a comment |

G B · Accepted Answer · 2023-09-06 06:31:07Z

5

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.

edited Sep 6 at 6:31

answered Sep 5 at 15:08

G B

21.3k1 gold badge19 silver badges51 bronze badges

\$\begingroup\$ 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 \$\endgroup\$
– Value Ink
Sep 6 at 1:12
1

\$\begingroup\$ @ValueInk it does not work for bases >= 12, because a single digit can be 11. For example f[27] is [3, 16] \$\endgroup\$
– G B
Sep 6 at 6:22

Add a comment |

bstrat · Accepted Answer · 2023-10-31 22:43:25Z

5

K (ngn/k), 28 26 bytes

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

-2 thanks to @coltim

Try it online!

edited Oct 31 at 22:43

answered Sep 8 at 7:55

bstrat

3011 silver badge4 bronze badges

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

Add a comment |

matteo_c · Accepted Answer · 2023-09-05 10:39:04Z

4

Haskell, 74 bytes

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!

answered Sep 5 at 10:39

matteo_c

5,80310 silver badges22 bronze badges

Add a comment |

Kevin Cruijssen · Accepted Answer · 2023-09-08 14:56:36Z

05AB1E, 12 11 bytes

tL¦ʒIÝmŒOIå

-1 byte thanks to @MTN by porting tL¦ from @JonathanAllan's Jelly answer.

Try it online or verify all test cases.

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)

\$\begingroup\$ 11 bytes (see Jonathan Allan's Jelly answer) \$\endgroup\$
– MTN
Sep 8 at 14:53 — MTN, Sep 8 at 14:53

ZaMoC · Accepted Answer · 2023-09-10 13:25:38Z

4

Wolfram Language (Mathematica), 58 bytes

Select[r=Range[0,#-2],Tr/@Subsequences[#^r]&/*MemberQ[#]]&

Try it online!

-2 bytes from @att

edited Sep 10 at 13:25

answered Sep 6 at 6:42

ZaMoC

24.4k2 gold badges29 silver badges79 bronze badges

\$\begingroup\$ 58 bytes \$\endgroup\$
– att
Sep 9 at 19:44

Add a comment |

alephalpha · Accepted Answer · 2023-09-11 02:32:21Z

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.

Kjetil S · Accepted Answer · 2023-09-08 15:21:13Z

3

Perl 5, 88 bytes

sub{grep{$x=$_;join('+',map$x**$_,0..$n)=~/\b.+\b(??{$n-eval$&?$;:""})/}2..sqrt($n=pop)}

Try it online!

answered Sep 8 at 15:21

Kjetil S

5,4879 silver badges17 bronze badges

Add a comment |

138 Aspen · Accepted Answer · 2023-09-09 12:20:15Z

3

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}\$

answered Sep 9 at 12:20

138 Aspen

4,7751 gold badge3 silver badges13 bronze badges

Add a comment |

Stack Exchange Network

Sum of consecutive nth powers

14 Answers 14

JavaScript (V8), 62 bytes

Algorithm

Explanation

C (gcc), 79 bytes

Vyxal, 73 bits^v2, 9.125 bytes

Explained

Charcoal, 24 20 bytes

Jelly, 10 bytes

How?

Python, 82 bytes

Haskell, 54 bytes

Ruby, 55 56 bytes

K (ngn/k), 28 26 bytes

Haskell, 74 bytes

05AB1E, 12 11 bytes

Wolfram Language (Mathematica), 58 bytes

Nekomata, 9 bytes

Nekomata, 10 bytes

Perl 5, 88 bytes

Scala 3, 85 bytes

Your Answer

Not the answer you're looking for? Browse other questions tagged
code-golf
math
integer
or ask your own question.

Linked

Hot Network Questions

Sum of consecutive nth powers

14 Answers 14

JavaScript (V8), 62 bytes

Algorithm

Explanation

C (gcc), 79 bytes

Vyxal, 73 bitsv2, 9.125 bytes

Explained

Charcoal, 24 20 bytes

Jelly, 10 bytes

How?

Python, 82 bytes

Haskell, 54 bytes

Ruby, 55 56 bytes

K (ngn/k), 28 26 bytes

Haskell, 74 bytes

05AB1E, 12 11 bytes

Wolfram Language (Mathematica), 58 bytes

Nekomata, 9 bytes

Nekomata, 10 bytes

Perl 5, 88 bytes

Scala 3, 85 bytes

Your Answer

Sign up or log in

Post as a guest

Not the answer you're looking for? Browse other questions tagged code-golfmathinteger or ask your own question.

Linked

Related

Hot Network Questions

Vyxal, 73 bits^v2, 9.125 bytes

Not the answer you're looking for? Browse other questions tagged
code-golf
math
integer
or ask your own question.