Stackable and unstackable numbers

Question

Consider boxes stacked on top of each other.

Boxes on the bottom row are labeled 1.

Boxes not on the bottom row must be supported directly below, and are labeled as the sum of the 2 or 3 boxes they are directly above, including diagonally.

Examples: The first 9 numbers can be generated like this: (Ignore the dots that are only meant to help you identify the horizontal position of the numbers.)

1	2.	.3.	4.	5..	.6..	.7.	.8..	..9..
.	11	111	22	23.	.33.	232	233.	.333.
.	..	...	11	111	1111	111	1111	11111

The challenge: List the numbers that cannot be generated this way. We call these numbers 'unstackable'.

Input: A positive integer n.

Output: [a_1, a_2, ..., a_n], the list of the first n unstackable numbers. This list might be an array or given term at term, at your option.

Test cases:

n	1	2	12	19	30
a(n)	11	31	139	199	263

Credits: Erich Friedman proposed this sequence to the OEIS, still under consideration.

This is code-golf, so each language's shortest code in bytes wins.

Answer 1

JavaScript (V8), 150 bytes

Prints the sequence forever (slowly).

for(n=9;a=[];o<n&&print(n))for(++n;a.push(1)<n;g(a))g=(a,p)=>a[i=1]<n&&g([p,...a]=a.map(v=>(v+=~-p-~a[p=v,i++])-n?v:o=n))&a.pop(g(a))&g(a)&g([p,...a])

Try it online!

Commented

for( // outer loop:
 n = 9; // start with n = 9 (*)
 a = []; // start each iteration with a = []
 o < n && print(n) // if o < n, n is unstackable -> print it
) //
 for( // inner loop:
 ++n; // increment n
 a.push(1) < n; // push 1 in a[], stop if a[] has n elements
 g(a) // invoke g with a[]
 ) //
 g = ( // g is a recursive function taking:
 a, // a[] = current row
 p // p = variable required in the scope of g,
 ) => // initially undefined
 a[i = 1] < n && // stop if a[1] >= n or a[1] is undefined
 g( // otherwise, do a 1st recursive call:
 [p, ...a] = // save the result of map() in p and a[]
 a.map(v => // for each value v in a[]:
 ( v += // compute the sum of the boxes
 ~-p - ~a[ // below the current box: v + p + a[i]
 p = v, // update p to v
 i++ // increment i
 ] //
 ) - n ? // if the result is not n:
 v // just yield v
 : // else:
 o = n // n is stackable -> update o to n
 ) // end of map()
 ) // end of recursive call()
 & a.pop(g(a)) // 2nd call without the 1st term
 & g(a) // 3rd call without the 1st and last terms
 & g([p, ...a]) // 4th call without the last term

_{(*) We can safely ignore \$n=1\$ to \$n=9\$ which are all stackable. Besides, our code would not work for \$n\in[1\dots3]\$. But we do need to process a stackable number (\$n=10\$) before processing the first unstackable one (\$n=11\$) to make sure that the variable \$o\$ is defined before it's tested.}

Answer 2

Charcoal, 85 bytes

NθW‹Lυθ«→≔...1X3iυ≔E⊕⊗iE⊕κ1ηFη«≔−υκυ≔EκΣ✂κ∧μ⊖μ+2μ1κFE2✂κλFE2✂⮌λμ¿∧μ∧‹⌊μX3i¬Noημ⊞ημ»»I...υθ

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

Nθ

Input n.

W‹Lυθ«

Repeat until at least n unstackable numbers have been found.

→

Start considering wider and taller stacks.

≔...1X3iυ

Consider unstackable numbers up to a value of 3x.

≔E⊕⊗iE⊕κ1η

Consider stacks with bases of widths 1 to 2x+1.

Fη«

Loop over each stack.

≔−υκυ

Remove any stackable numbers.

≔EκΣ✂κ∧μ⊖μ+2μ1κ

Calculate the next layer.

FE2✂κλFE2✂⮌λμ

Consider the layer with the first and/or last element(s) removed.

¿∧μ∧‹⌊μX3i¬Noημ⊞ημ

If this is a new stack and not too tall then add this stack for further consideration.

»»I...υθ

Output the first n unstackable numbers.

Answer 3

05AB1E, 36 bytes

∞ʒÐUÅ1"DXa1èX‹iŒε0.øü3OD®.V)"©.V ̃Xå≠

Outputs the infinite sequence. Unfortunately, it's extremely slow, so barely even outputs \$a(1)=11\$ within 60 seconds on TIO..

(Don't) try it online.

Explanation:

∞ # Push the infinite positive list: [1,2,3,...]
 ʒ # Filter it by:
 DU # Store a copy of the current value in variable `X`
 Å1 # Push a list of that many 1s
 "..." # Push the recursive string explained below
 © # Store this string in variable `®`
 .V # Pop and evaluate it as 05AB1E code
 ̃ # Flatten it
 Xå # Check whether `X` is in this flattened list
 ≠ # Invert the check, since we only want unstackable numbers
 # (after which the filtered infinite list is lazily output
 # implicitly)
D # Create a copy of the current list
 Xa # Append `X` in case the list is of length 1
 1è # Pop and get the second item (0-based 1st)
 X‹i # If it's still smaller than `X`, continue:
 Π# Get all substrings of this list
 ε # Map over each substring:
 0.ø # Surround it with a leading and trailing 0
 ü3 # Pop and get all overlapping triplets
 O # Sum each overlapping triplet
 D # Duplicate this list of sums
 ®.V # Do a recursive call on the copy
 ) # Wrap everything currently on the stack into a list

Answer 4

Python3, 498 bytes

lambda:sorted({*range(1,max(k:={j for k in range(1,20)for j in F(k,700)})+1)}-k)
def F(b,C):
 q,S=[([1]*b,[])],[]
 for b,t in q:
 if any(k>C for k in b):continue
 if len(b)==1:yield b[0];continue
 Q=[(0,[0]*len(b),b)]*(b!=[])
 for I,r,B in Q:
 if I==len(r):q+=[T:=([k for k in r if k],t+[b])]*(T not in S);S+=[T];continue
 if I==0 or I==len(r)-1:Q+=[(I+1,r,B)]
 for m in[[I-1,I,I+1],[I,I+1],[I-1,I]]:
 if all(len(r)>i>=0 for i in m):R=[*r];R[I]=sum(B[u]for u in m);Q+=[(I+1,R,B)];break

Try it online!

• ceilingcat: 487 bytes

Answer 5

Perl 5, 232 bytes

@S=0..($m=20*($N=pop));sub f{@S[@_]=();!$s{"@$_"}++&&(grep$_&&$m>$_,@$_)&&f(@$_)for[0,@_[2..$#_]],[@_[0..@_-3],0],[0,@_[2..@_-3],0],[0,(map$_[$_+1]?$_[$_]+$_[$_+1]+$_[$_+2]:0,0..@_-3),0]}f(0,(1)x(8+$N/20),0);$_&&$N&&$N--&&say for@S;

Try it online!