Sequence of integers not the sum of powers of earlier terms

Question

Starting with 1, output the sequence of integers which cannot be represented as the sum of powers of earlier terms. Each previous term can be used at most once, and the exponents must be non-negative integers.

This sequence starts:

1, 2, 6, 12, 25, 85, 194, 590, 1695, 4879, 19077, 83994, 167988

For example, after 1 and 2:

• \$ 3 = 1^1 + 2^1 \$, so 3 is not in the sequence
• \$ 4 = 2^2 \$, so 4 is not in the sequence
• \$ 5 = 1^1 + 2^2 \$, so 5 is not in the sequence
• \$ 6 \$ cannot be represented in this way, so 6 is in the sequence
• etc.

The powers can also be 0; for example, \$ 24 = 1^1+2^4+6^1+12^0 \$, so 24 is not in the sequence.

This is OEIS A034875.

Rules

• As with standard sequence challenges, you may choose to either:
  • Take an input n and output the nth term of the sequence
  • Take an input nand output the first n terms
  • Output the sequence indefinitely, e.g. using a generator
• You may use 0- or 1-indexing
• You may use any standard I/O method
• Standard loopholes are forbidden
• This is code-golf, so the shortest code in bytes wins

Answer 1

Python 3, ^{121 107 105 102} 101 bytes

-3 inspired by Neil's comments, and another -1 thanks to Neil!

Prints the sequence indefinitely. Runs out of memory before finding 25 on TIO.

d,*r=0,
while m:=1:
 d+=1
 for v in r:
  w=m
  for p in range(d):m|=w<<v**p
 if~m>>d&1:r+=d,;print(d)

Try it online!

---

Python 3, 186 178 166 bytes

Fast version, produces all terms on the OEIS page in 2 minutes locally. Assuming this is correct, the next two terms are \$3828253274\$ and \$24694834727\$. Because of the time is spent in arithmetic with large numbers (native code), a naïve C+gmp translation is only ~2 times faster, and very ungolfy.

m=d=1;r=[]
print(1)
while q:=3:
 s=(~m&m+1).bit_length()-1;d+=s;m>>=s
 for v in r:
  w=q;l=1
  while l<=d:q|=w<<l;l*=v
  if q&1<<d:break
 else:r+=d,;print(d)
 m|=q>>d

Try it online!

Answer 2

Jelly, 24 22 bytes

*þṀŻ$ZŒpŒP€Ẏ§‘ḟ$Ṃ;
⁸Ç¡

Try it online!

Takes \$n\$ via STDIN and outputs the first \$n\$ terms in reverse order. +1 byte if the output has to be in ascending order.

Incredibly slow, can handle up to \$n = 4\$ on TIO. If \$a_n\$ is our sequence so far, then, to generate \$a_{n+1}\$, the code runs in approximately \$O((2a_n + 2)^n)\$ time.

-2 bytes thanks to Jonathan Allan

How it works

*þṀŻ$ZŒpŒP€Ẏ§‘ḟ$Ṃ; - Helper link. Given a list L of integers, returns the list with the next term prepended
    $              - To L:
  Ṁ                -   Maximum
   Ż               -   [0, ..., max(L)]
 þ                 - Over each pair (l, i), l ∈ L, i ∈ [0, ..., max(L)]:
*                  -   Raise l to the ith power
     Z             - Transpose
      Œp           - Cartesian product of rows
        ŒP€        - Powerset of each
           Ẏ       - Collapse into a list of lists
            §      - Sums
               $   - To our list of sums:
             ‘     -   Increment
              ḟ    -   Remove elements in the list of sums
                Ṃ  - Minimum
                 ; - Prepend it to L

⁸Ç¡                  - Main link. No arguments.
⁸                    - Set the return value to []
  ¡                  - Read n from STDIN. Starting with [], do n times:
 Ç                   -   Call the helper link, updating the argument with the previous return value each time

---

Alternatively, a much faster version at 36 bytes that can do up to \$n = 8\$ on TIO.

Answer 3

Jelly, 22 bytes

-rṀṗL‘a*@ɗ⁸§‘ḟ$Ṃ;@
⁸Ç¡

A full program that accepts an integer, n, from STDIN and prints the Jelly representation of the first n terms so STDOUT.

Try it online! (6 will time out on TIO.)

How?

-rṀṗL‘a*@ɗ⁸§‘ḟ$Ṃ;@ - Link 1, getNext: list KnownTerms
  Ṁ                - maximum of KnownTerms (given an empty list yields 0)
-                  - -1
 r                 - inclusive range -> Exponents (-1 is an indicator to exclude the base)
    L              - length of KnownTerms
   ṗ               - Cartesian power -> all sets of exponents of size NumberOfTerms
         ɗ⁸        - last three links as a dyad - f(Sets, KnownTerms)
     ‘             - increment all Exponents in the Sets
       *@          - KnownTerms exponentiate Sets (vectorises)
      a            - logical AND (vectorises) (i.e. replace with 0 when the exponent was -1)
           §       - sums
              $    - last two links as a monad:
            ‘      -   increment all the found values
             ḟ     -   filter out the found values
               Ṃ   - minimum
                ;@ - concatenate to KnownTerms

⁸Ç¡ - Main Link: no arguments
⁸   - empty list
  ¡ - repeat...
    - ...times: implicitly take an integer from STDIN
 Ç  - ...action: call Link 1 as a monad
    - implicit print

Answer 4

JavaScript (V8), 104 bytes

Prints the sequence forever. Not tremendously fast, but fast enough to reach \$19077\$ on TIO.

for(a=N=[];;g``||a.push(N)&print(N))g=(q,i=1,n=++N)=>n<0|!a[i]?0:n<2||g(Q=q*a[i]||1,i,n+q-Q)||g(0,i+1,n)

Try it online!

Note

The way this algorithm works, it would be a bit painful to use \$1^k\$ because we'd need some extra testing to avoid an infinite loop. Instead, we don't use it at all and try to reach either \$n\$ or \$n-1\$ with the other integers. This is why the search function \$g\$ starts at index \$i=1\$ in the array \$a[\:]\$.

---

JavaScript (V8), 101 bytes

Slower but a little shorter.

for(a=N=[];;g``||a.push(N)&print(N))g=(q,i=1,n=++N)=>n*a[i]>=0&&n<2|g(Q=q*a[i]||1,i,n+q-Q)|g(0,i+1,n)

Try it online!

Answer 5

Charcoal, 42 bytes

Ｎθ≔⁰ηＷ‹Ｌυθ«≦⊕η≔⟦η⟧ζＦυＦ⮌ζＦλ⊞ζ⁻λＸκμ¿Πζ⊞υη»Ｉυ

Try it online! Link is to verbose version of code. Explanation: Port of @ovs' Python answer, except outputs the first n terms.

Ｎθ

Input n.

≔⁰η

Start looking for terms.

Ｗ‹Ｌυθ«

Repeat until enough terms have been found.

≦⊕η

Try the next integer.

≔⟦η⟧ζ

Start with a list of just that integer, corresponding to no powers of earlier terms yet.

Ｆυ

For each earlier term...

Ｆ⮌ζ

... for each value in a (reversed because it's the golfiest way to) copy of the list...

Ｆλ⊞ζ⁻λＸκμ

... subtract some powers of the earlier term and add the results to the list.

¿Πζ⊞υη

If there were no zeros in the list (i.e. the product is nonzero), meaning that no sums of powers added to the current integer, then add it as a term.

»Ｉυ

Output all of the found terms.

76 74 bytes for a somewhat faster version based on @ovs' faster version:

Ｎθ≔³ε≔⁰ζ⊞υ¹Ｗ‹Ｌυθ«Ｗ＆εＸ²ζ≦⊕ζ≔³εＦυ«≔εδ≔¹ιＷ∧⊖꬛ιζ«≧｜×δＸ²ιε≧×κι»»¿¬＆εＸ²ζ⊞υζ»Ｉυ

Try it online! Link is to verbose version of code.

Answer 6

Python 3, 179 bytes

from itertools import*
def f(n):
	x,N=[1],2
	while len(x)<n:x=[x+[N],x][N in[sum([N**p for N,p in zip(x,e)if-1<p])for e in product(*[list(range(-1,N))for _ in x])]];N+=1
	return x

Try it online!

It is quite slow, the TIO link will only let you test up to n=5

Explanation

from itertools import*
def f(n):
    x,N=[1],2                                                              # Initialise the list, start testing from 2
    while len(x)<n:                                                        # Condition to get the first n terms of the sequence
                   [N in                                                   # Returns False (indexes 0) if N not in list,
        x=[x+[N],                                                          # appending N to the list,
                 x]                                                        # else leave the list unchanged
                        [sum([N**p for N,p in zip(x,e)                     # Sum of the previous sequence terms raised to their respective powers,
                            if-1<p])                                       # unless it's not in this permutation (a power of -1 is used to represent a 0 multiplier)
                                for e in product(                          # Permutations of the possible powers for the previous terms of the sequence
                                    *[list(range(-1,N))for _ in x])]];     # Possible powers for each previous term of the sequence.
                                                                      N+=1 # Increment number
    return x                                                               # Return the sequece

The main reason this runs so slow is because there are so many permutations for all the powers, and because list comprehension is used it has to calculate all permutations. Currently all possible powers from 0 to n-1 are considered, as this was the shortest way to do it in bytes (and still theoretically be able to calculate for any n). A faster solution would be to limit the possible powers, for example by replacing [list(range(-1,N))for _ in x] with ([[-1,0]]+[[-1]+[i for i in range(int(math.log(N,j))+1)]for j in x[1:]]), which only lets each term go up to the power such that \$t_i^p<N\$

Answer 7

Ruby, 93 bytes

*r=p a=1;a+=1while[a]-[0].product(*r.map{|w|[0]+(0..a).map{|e|w**e}}).map(&:sum)==[]||r<<p(a)

Try it online!

Answer 8

Perl 5, 119 bytes

while(){map{$o=$_;my$s;map{$s+=$o%$m?$_**($o%$m-1):0;$s-$t||next;$o/=$m}@s}0..($m=2+log(++$t)/.69)**@s;push@s,$t;say$t}

Try it online!

Dog slow. Try it online found 1, 2, 6, 12, 25, 85, 194 within its 60 second timeout. Same code found 85 within 0.7 seconds on my laptop, 194 within 8 seconds and 590 took 14 minutes.

Answer 9

05AB1E, 28 bytes

2Lλ∞λ©K.Δ®sÝδm0δšÅ»â}θ€˜Oyå≠

Outputs the infinite sequence.

Should have been 27 bytes, but a regular reduce-by .ȉ} instead of 'keep last after cumulative reduce-by' Å»â}θ doesn't work for some reason.. :/

Try it online.

Explanation:

  λ            # Start a recursive environment,
               # to generate the infinite sequence
2L             # Starting with a(0)=1 and a(1)=2
               # Where every next a(n) is calculated as:
   ∞           #  Push an infinite positive list [1,2,3,...]
    λ          #  Push a list of all previous terms [a(0),a(1),...,a(n-1)]
     ©         #  Store it in variable `®` (without popping)
      K        #  Remove those values from the infinite list
   .Δ          #  Then find the first value which is truthy for:
     ®         #   Push the list of previous terms `®`
      s        #   Swap so the current value is at the top
       Ý       #   Pop and push a list in the range [0,value]
        δ      #   Apply double-vectorized:
         m     #    Exponentiation
           δ   #   Map over each inner list:
          0 š  #    Prepend a 0
     Å»        #   Cumulative right-reduce by:
       â       #    Cartesian product of both list to create pairs
      }θ       #   After the cumulative right-reduce, leave the final result
        €˜     #   Flatten each inner list
          O    #   Sum each inner list
           yå≠ #   Check that the current value is NOT in this list of sums
               #   (after which the result is output implicitly)