A268361 Lexicographically least sequence of a certain form that avoids additive squares.

1, 2, 1, 3, 1, 2, 1, 5, 1, 2, 1, 3, 1, 2, 1, 8, 1, 2, 1, 3, 1, 2, 1, 5, 1, 2, 1, 3, 1, 2, 1, 13, 1, 2, 1, 3, 1, 2, 1, 5, 1, 2, 1, 3, 1, 2, 1, 8, 1, 2, 1, 3, 1, 2, 1, 5, 1, 2, 1, 3, 1, 2, 1, 21, 1, 2, 1, 3, 1, 2, 1, 5, 1, 2, 1, 3, 1, 2, 1, 8, 1, 2, 1, 3, 1

Offset

1,2

Comments

An "additive square" consists of two consecutive blocks of the same length, with the same sum. This sequence a is the lexicographically least sequence over the natural numbers, having no additive square, which is of the form a(i) = b(A001511(i)) for some sequence b.

Links

Robert Israel, Table of n, a(n) for n = 1..10000

Chen Fei Du, Hamoon Mousavi, Luke Schaeffer, and Jeffrey Shallit, Decision Algorithms for Fibonacci-Automatic Words, with Applications to Pattern Avoidance, arXiv:1406.0670 [cs.FL], 2014.

Formula

a(n) = A000045(A001511(n)+1).

G.f.: Sum_{j>=1} A000045(j+1)*x^(2^(j-1))/(1-x^(2^j)). - Robert Israel, Feb 03 2016

Multiplicative with a(2^e) = Fibonacci(2 + e), a(p^e) = 1 for odd prime p. - Andrew Howroyd, Aug 02 2018

Asymptotic mean: Limit_{m->oo} (1/m) * Sum_{k=1..m} a(k) = 3. - Amiram Eldar, Nov 30 2022

Maple

f:= n -> combinat:-fibonacci(padic:-ordp(2*n, 2)+1):
map(f, [$1..100]); # Robert Israel, Feb 03 2016

Mathematica

a[n_] := Fibonacci[IntegerExponent[2n, 2] + 1];
Array[a, 100] (* Jean-François Alcover, Aug 29 2018 *)

Prog

(PARI) a(n)=fibonacci(2 + valuation(n, 2)) \\ Andrew Howroyd, Aug 02 2018

Crossrefs

Cf. A000045, A001511.

Sequence in context: A059127 A319494 A105609 * A330569 A340785 A355758

Adjacent sequences: A268358 A268359 A268360 * A268362 A268363 A268364

Keyword

nonn,mult

Author

Jeffrey Shallit, Feb 03 2016

Status

approved