23
\$\begingroup\$

Related.

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:

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

14 Answers 14

10
\$\begingroup\$

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.

\$\endgroup\$
7
\$\begingroup\$

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.

\$\endgroup\$
7
\$\begingroup\$

Charcoal, 24 20 bytes

NθIΦ…²⊖θ¬⊙⪪⍘θι0⁻λI¬μ

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.

Nθ                      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
                 I      Cast to string
                        Implicitly print
\$\endgroup\$
1
  • 3
    \$\begingroup\$ Nice observation! \$\endgroup\$
    – MTN
    Sep 5 at 9:23
7
\$\begingroup\$

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)
\$\endgroup\$
7
\$\begingroup\$

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

\$\endgroup\$
2
  • \$\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
5
\$\begingroup\$

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!

\$\endgroup\$
5
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\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
5
\$\begingroup\$

K (ngn/k), 28 26 bytes

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

-2 thanks to @coltim

Try it online!

\$\endgroup\$
1
  • \$\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
4
\$\begingroup\$

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!

\$\endgroup\$
4
\$\begingroup\$

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)
\$\endgroup\$
1
  • 2
    \$\begingroup\$ 11 bytes (see Jonathan Allan's Jelly answer) \$\endgroup\$
    – MTN
    Sep 8 at 14:53
4
\$\begingroup\$

Wolfram Language (Mathematica), 58 bytes

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

Try it online!

-2 bytes from @att

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

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.

\$\endgroup\$
3
\$\begingroup\$

Perl 5, 88 bytes

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

Try it online!

\$\endgroup\$
3
\$\begingroup\$

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

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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