A379739 Subdiagonal of the Hurt-Sada array.

2, 3, 4, 3, 7, 8, 9, 6, 7, 13, 14, 9, 10, 18, 19, 12, 13, 23, 24, 25, 16, 28, 29, 30, 19, 20, 34, 35, 22, 23, 39, 40, 25, 26, 44, 45, 46, 29, 49, 50, 51, 32, 54, 55, 56, 35, 36, 60, 61, 38, 39, 65, 66, 67, 42, 70, 71, 72, 45, 75, 76, 77, 48, 49, 81, 82, 51

Offset: 1

Author

Jeffrey Shallit, Jan 14 2025

Keywords

• nonn

Comments

The array is depicted in A368050.

Links

• Charles R Greathouse IV, Table of n, a(n) for n = 1..10000
• Jeffrey Shallit, Automaton deciding whether a(n) >= n
• Jeffrey Shallit, The Hurt-Sada Array and Zeckendorf Representations, arXiv:2501.08823 [math.NT], 2025. See p. 2.

Crossrefs

Cf. A368050, A380079.

Programs

PARI

zeckendorf(n)=my(f1=1,f2=2,fibs=List([1]),rep=List(),i); while(f2<=n,listput(fibs,f2);[f1,f2]=[f2,f1+f2];); i=#fibs; while(i,if(fibs[i]>n, i--, listput(rep,1); n-=fibs[i]; if(i==1,break); i-=2); listput(rep,0)); Vec(rep)
a(n)=my(g=quadgen(5), Z=zeckendorf(n), state=1, new0=[1, 3, 4, 6, 3, 8, 6, 8], new1=[2, 0, 5, 7, 0, 5, 0, 2]); for(i=1, #Z, state=if(Z[i], new1, new0)[state]); if(state!=5 && state!=8, 2*n/g+1, (4-2*g)*n + (5-3*g))\1 \\ Charles R Greathouse IV, Jan 14 2025

Formula

If a(n) < n, then a(n) = floor((4-2*g)n + (5-3*g)), where g = (1+sqrt(5))/2, the golden ratio. If a(n) >= n, then a(n) = floor((2*g-2)n) + 1. There is an 8-state automaton (see the links section) that takes the Zeckendorf representation of n as input and decides whether a(n) >= n.