A115004 -id:A115004 - cp's OEIS frontend

A014675 The infinite Fibonacci word (start with 1, apply 1->2, 2->21, take limit).

2, 1, 2, 2, 1, 2, 1, 2, 2, 1, 2, 2, 1, 2, 1, 2, 2, 1, 2, 1, 2, 2, 1, 2, 2, 1, 2, 1, 2, 2, 1, 2, 2, 1, 2, 1, 2, 2, 1, 2, 1, 2, 2, 1, 2, 2, 1, 2, 1, 2, 2, 1, 2, 1, 2, 2, 1, 2, 2, 1, 2, 1, 2, 2, 1, 2, 2, 1, 2, 1, 2, 2, 1, 2, 1, 2, 2, 1, 2, 2, 1, 2, 1, 2, 2, 1, 2, 2, 1, 2, 1, 2, 2

Offset: 0

N. J. A. Sloane

The limiting mean and variance of the first n terms are both equal to the golden ratio (A001622). - Clark Kimberling, Mar 12 2014
Let F = A000045 (Fibonacci numbers).  For n >= 3, the first F(n)-2 terms of A014675 form a palindrome; see A001911.  If k is not one of the numbers F(n)-2, then the first k terms of A014675 do not form a palindrome. - Clark Kimberling, Jul 14 2014
First differences of A000201. - Tom Edgar, Apr 23 2015 [Editor's note: except for the offset: as for A022342, below. - M. F. Hasler, Oct 13 2017]
Also first differences of A022342 (which starts at offset 1): a(n)=A022342(n+2)-A022342(n+1), n >= 0. Equal to A001468 without its first term: a(n) = A001468(n+1), n >= 0. - M. F. Hasler, Oct 13 2017
The word is a concatenation of three runs: 1, 2, and 22. The limiting proportions of these are respectively 1/2, 1 - phi/2, and (phi - 1)/2, where phi = golden ratio.  The mean runlength is (phi + 1)/2. - Clark Kimberling, Dec 26 2010

D. Gault and M. Clint, "Curiouser and curiouser" said Alice. Further reflections on an interesting recursive function, Internat. J. Computer Math., 26 (1988), 35-43. See Table 2.
D. E. Knuth, The Art of Computer Programming, Vol. 4A, Section 7, p. 36.
G. Melançon, Factorizing infinite words using Maple, MapleTech journal, vol. 4, no. 1, 1997, pp. 34-42, esp. p. 36.

T. D. Noe, Table of n, a(n) for n = 0..10945 (20 iterations)
M. Bunder and K. Tognetti, On the self matching properties of [j tau], Discrete Math., 241 (2001), 139-151.
D. Gault and M. Clint, "Curiouser and curiouser said Alice. Further reflections on an interesting recursive function, Intern. J. Computer. Math., 26 (1988), 35-43. (Annotated scanned copy)
J. Grytczuk, Infinite semi-similar words, Discrete Math. 161 (1996), 133-141.
G. Melançon, Lyndon factorization of sturmian words, Discr. Math., 210 (2000), 137-149.
N. J. A. Sloane, Families of Essentially Identical Sequences, Mar 24 2021 (Includes this sequence)
Index entries for sequences that are fixed points of mappings

This is the {2,1} version. The standard form is A003849 (alphabet {0,1}). See also A005614 (alphabet {1,0}), A003842 (alphabet {1,2} instead of {2,1}).
Cf. A082389, A008351, A000045, A001622, A001911.
Equals A001468 except for initial term.
Differs from A025143 in many entries starting at entry 8.
First differences of A000201 and of A022342.
The following sequences are all essentially the same, in the sense that they are simple transformations of each other, with A000201 as the parent: A000201, A001030, A001468, A001950, A003622, A003842, A003849, A004641, A005614, A014675, A022342, A088462, A096270, A114986, A124841. - N. J. A. Sloane, Mar 11 2021

Digits := 50: t := evalf( (1+sqrt(5))/2); A014675 := n->floor((n+2)*t)-floor((n+1)*t);

Nest[ Flatten[ # /. {1 -> 2, 2 -> {2, 1}}] &, {1}, 11] (* Robert G. Wilson v *)
SubstitutionSystem[{1->{2},2->{2,1}},{1},{11}][[1]] (* Harvey P. Dale, Jan 01 2023 *)

first(n)=my(v=[1],u); while(#vCharles R Greathouse IV, Jun 21 2017

apply( {A014675(n,r=quadgen(5)-1)=(n+2)\r-(n+1)\r}, [0..99]) \\ M. F. Hasler, Apr 07 2021, improved on suggestion from Kevin Ryde, Apr 23 2021

from math import isqrt
def A014675(n): return (n+2+isqrt(m:=5*(n+2)**2)>>1)-(n+1+isqrt(m-10*n-15)>>1) # Chai Wah Wu, Aug 10 2022

Define strings S(0)=1, S(1)=2, S(n)=S(n-1).S(n-2) for n>=2. Sequence is S(infinity).

a(n) = floor((n+2)*phi) - floor((n+1)*phi) = A000201(n+2) - A000201(n+1), phi = (1 + sqrt(5))/2.

Corrected by N. J. A. Sloane, Nov 07 2001

A000057 Primes dividing all Fibonacci sequences.

Original entry on oeis.org

2, 3, 7, 23, 43, 67, 83, 103, 127, 163, 167, 223, 227, 283, 367, 383, 443, 463, 467, 487, 503, 523, 547, 587, 607, 643, 647, 683, 727, 787, 823, 827, 863, 883, 887, 907, 947, 983, 1063, 1123, 1163, 1187, 1283, 1303, 1327, 1367, 1423, 1447, 1487, 1543, 1567, 1583

Offset: 1

N. J. A. Sloane

nonn

Here a Fibonacci sequence is a sequence which begins with any two integers and continues using the rule s(n+2) = s(n+1) + s(n). These primes divide at least one number in each such sequence. - Don Reble, Dec 15 2006
Primes p such that the smallest positive m for which Fibonacci(m) == 0 (mod p) is m = p + 1. In other words, the n-th prime p is in this sequence iff A001602(n) = p + 1. - Max Alekseyev, Nov 23 2007
Cubre and Rouse comment that this sequence is not known to be infinite. - Charles R Greathouse IV, Jan 02 2013
Number of terms up to 10^n: 3, 7, 38, 249, 1894, 15456, 130824, 1134404, 10007875, 89562047, .... - Charles R Greathouse IV, Nov 19 2014
These are also the fixed points of sequence A213648 which gives the minimal number of 1's such that n*[n; 1,..., 1, n] = [x; ..., x], where [...] denotes simple continued fractions. - M. F. Hasler, Sep 15 2015
It appears that for n >= 2, all first differences are congruent to 0 (mod 4). - Christopher Hohl, Dec 28 2018
The comment above is equivalent to a(n) == 3 (mod 4) for n >= 2. This is indeed correct. Actually it can be proved that a(n) == 3, 7 (mod 20) for n >= 2. Let p != 2, 5 be a prime, then: A001175(p) divides (p - 1)/2 if p == 1, 9 (mod 20); p - 1 if p == 11, 19 (mod 20); (p + 1)/2 if p == 13, 17 (mod 20). So the remaining cases are p == 3, 7 (mod 20). - Jianing Song, Dec 29 2018

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Christian G. Bower and T. D. Noe, Table of n, a(n) for n = 1..1000
U. Alfred, Primes which are factors of all Fibonacci sequences, Fib. Quart., 2 (1964), 33-38.
B. Avila and T. Khovanova, Free Fibonacci Sequences, arXiv preprint arXiv:1403.4614 [math.NT], 2014 and J. Int. Seq. 17 (2014) # 14.8.5.
D. M. Bloom, On periodicity in generalized Fibonacci sequences, Am. Math. Monthly 72 (8) (1965) 856-861.
H. E. A. Campbell and David L. Wehlau, Zigzag polynomials, Artin's conjecture and trinomials, Finite Fields and Their Applications (2023) Vol. 89, 102198.
Paul Cubre and Jeremy Rouse, Divisibility properties of the Fibonacci entry point, arXiv:1212.6221 [math.NT], 2012.
Ron Knott, General Fibonacci Series.
Rishi Kumar, Kepler Sets of Second-Order Linear Recurrence Sequences Over Q_p, arXiv:2406.05890 [math.NT], 2024. See pp. 2, 7.
N. J. A. Sloane, Families of Essentially Identical Sequences, Mar 24 2021 (Includes this sequence).

Subsequence of A064414.

Cf. A001175, A001602, A079346, A106535, A213648.

Select[Prime[Range[1000]], Function[p, a=0; b=1; n=1; While[b != 0, t=b; b = Mod[(a+b), p]; a=t; n++]; n>p]] (* Jean-François Alcover, Aug 05 2018, after Charles R Greathouse IV *)

select(p->my(a=0,b=1,n=1,t);while(b,t=b;b=(a+b)%p; a=t; n++); n>p, primes(1000)) \\ Charles R Greathouse IV, Jan 02 2013

is(p)=fordiv(p-1,d,if(((Mod([1,1;1,0],p))^d)[1,2]==0,return(0)));fordiv(p+1,d,if(((Mod([1,1;1,0],p))^d)[1,2]==0,return(d==p+1 && isprime(p)))) \\ Charles R Greathouse IV, Jan 02 2013

is(p)=if((p-2)%5>1, return(0)); my(f=factor(p+1)); for(i=1, #f~, if((Mod([1, 1; 1, 0], p)^((p+1)/f[i, 1]))[1, 2]==0, return(0))); isprime(p) \\ Charles R Greathouse IV, Nov 19 2014

More terms from Don Reble, Nov 14 2006

A003151 Beatty sequence for 1+sqrt(2); a(n) = floor(n*(1+sqrt(2))).

Original entry on oeis.org

2, 4, 7, 9, 12, 14, 16, 19, 21, 24, 26, 28, 31, 33, 36, 38, 41, 43, 45, 48, 50, 53, 55, 57, 60, 62, 65, 67, 70, 72, 74, 77, 79, 82, 84, 86, 89, 91, 94, 96, 98, 101, 103, 106, 108, 111, 113, 115, 118, 120, 123, 125, 127, 130, 132, 135, 137, 140, 142, 144

Offset: 1

N. J. A. Sloane

Numbers with an odd number of trailing 0's in their minimal representation in terms of the positive Pell numbers (A317204). - Amiram Eldar, Mar 16 2022
From Clark Kimberling, Dec 24 2022: (Start)
This is the first of four sequences that partition the positive integers. Starting with a general overview, suppose that u = (u(n)) and v = (v(n)) are increasing sequences of positive integers. Let u' and v' be their complements, and assume that the following four sequences are infinite:
(1)  u ^ v = intersection of u and v (in increasing order);
(2)  u ^ v';
(3)  u' ^ v;
(4)  u' ^ v'.
Every positive integer is in exactly one of the four sequences.
For A003151, u, v, u', v', are the Beatty sequences given by u(n) = floor(n*sqrt(2)) and v(n) = floor(((1+sqrt(2))/2)*n), so that r = sqrt(2), s = (1+sqrt(2))/2, r' = (2+sqrt(2))/2, s' = 1 + 1/sqrt(2).
Assume that if w is any of the sequences u, v, u', v', then lim_{n->oo} w(n)/n exists and defines the (limiting) density of w. For w = u,v,u',v', denote the densities by r,s,r',s'. Then the densities of sequences (1)-(4) exist, and 1/(r*r') + 1/(r*s') + 1/(s*s') + 1/(s*r') = 1.
(1)  u ^ v = (2, 4, 7, 9, 12, 14, 16, 19, 21, 24, 26, 28, 31, 33, ...) = A003151
(2)  u ^ v' = (1, 5, 8, 11, 15, 18, 22, 25, 29, 32, 35, 39, 42, ...) = A001954
(3)  u' ^ v = (284, 287, 289, 292, 294, 296, 299, 301, 304, 306, ...) = A356135
(4)  u' ^ v' = (3, 6, 10, 13, 17, 20, 23, 27, 30, 34, 37, 40, 44, ...) = A003152
For results of compositions instead of intersections, see A184922. (End)
The indices of the twice squares in the sequence of squares and twice squares: A028982(a(n)) = 2*n^2. - Amiram Eldar, Apr 13 2025

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

G. C. Greubel, Table of n, a(n) for n = 1..5000
Shiri Artstein-Avidan, Aviezri S. Fraenkel and Vera T. Sós, A two-parameter family of an extension of Beatty sequences, Discrete Math., Vol. 308, No. 20 (2008), pp. 4578-4588; preprint.
Leonard Carlitz, Richard Scoville, and Verner E. Hoggatt, Jr., Pellian representatives, Fib. Quart., Vol. 10, No. 5 (1972), pp. 449-488.
Benoit Cloitre, N. J. A. Sloane, and Matthew J. Vandermast, Numerical analogues of Aronson's sequence, J. Integer Seq., Vol. 6 (2003), Article 03.2.2; arXiv preprint, arXiv:math/0305308 [math.NT], 2003.
Joshua N. Cooper and Alexander W. N. Riasanovsky, On the Reciprocal of the Binary Generating Function for the Sum of Divisors, J. Int. Seq., Vol. 16 (2013), Article 13.1.8; preprint, 2012.
R. J. Mathar, Graphical representation among sequences closely related to this one (cf. N. J. A. Sloane, "Families of Essentially Identical Sequences").
Luke Schaeffer, Jeffrey Shallit, and Stefan Zorcic, Beatty Sequences for a Quadratic Irrational: Decidability and Applications, arXiv:2402.08331 [math.NT], 2024. See pp. 17-18.
N. J. A. Sloane, Families of Essentially Identical Sequences, Mar 24 2021 (Includes this sequence).
Index entries for sequences related to Beatty sequences.

Complement of A003152.
Equals A001951(n) + n.
Cf. A028982, A109250, A317204.
The following sequences are all essentially the same, in the sense that they are simple transformations of each other, with A003151 as the parent: A003151, A001951, A001952, A003152, A006337, A080763, A082844 (conjectured), A097509, A159684, A188037, A245219 (conjectured), A276862. - N. J. A. Sloane, Mar 09 2021
Bisections: A197878, A215247.
Cf. A001954, A356135, A184922, A341239.

Table[Floor[n*(1 + Sqrt[2])], {n, 1, 50}] (* G. C. Greubel, Jul 02 2017 *)

for(n=1,50, print1(floor(n*(1 + sqrt(2))), ", ")) \\ G. C. Greubel, Jul 02 2017

from math import isqrt
def A003151(n): return n+isqrt(n*n<<1) # Chai Wah Wu, Aug 03 2022

a(1) = 2; for n>1, a(n+1) = a(n)+3 if n is already in the sequence, a(n+1) = a(n)+2 otherwise.

A006337 An "eta-sequence": a(n) = floor( (n+1)sqrt(2) ) - floor( nsqrt(2) ).

Original entry on oeis.org

1, 2, 1, 2, 1, 1, 2, 1, 2, 1, 1, 2, 1, 2, 1, 2, 1, 1, 2, 1, 2, 1, 1, 2, 1, 2, 1, 2, 1, 1, 2, 1, 2, 1, 1, 2, 1, 2, 1, 1, 2, 1, 2, 1, 2, 1, 1, 2, 1, 2, 1, 1, 2, 1, 2, 1, 2, 1, 1, 2, 1, 2, 1, 1, 2, 1, 2, 1, 1, 2, 1, 2, 1, 2, 1, 1, 2, 1, 2, 1, 1, 2, 1, 2, 1, 2, 1, 1, 2, 1, 2, 1, 1, 2, 1, 2, 1, 2, 1, 1, 2, 1, 2, 1, 1

Offset: 1

D. R. Hofstadter, Jul 15 1977

Defined by: (i) a(1) = 1; (ii) sequence consists of single 2's separated by strings of 1's; (iii) the sequence of lengths of runs of 1's in the sequence is equal to the sequence.
Equals its own "derivative", which is formed by counting the strings of 1's that lie between 2's.
First differences of A001951 (with a different offset). - Philippe Deléham, May 29 2006
Or number of perfect squares in interval (2*n^2, 2*(n+1)^2). In view of the uniform distribution mod 1 of sequence {sqrt(2)*n}, the density of 1's is 2-sqrt(2). - Vladimir Shevelev, Aug 05 2011
a(n) = number of repeating n's in A049472. - Reinhard Zumkeller, Jul 03 2015
Fixed point of the morphism 1 -> 12; 2 -> 121. - Jeffrey Shallit, Jan 19 2017
Also, let S be the increasing sequence of elements of the union N U N*sqrt(2), where N = {1, 2, 3, ...}. Then a(n) = { 1 if S(n) is integer, 2 if S(n) is irrational }. See A245222 for the analog with sqrt(3). - M. F. Hasler, Feb 06 2025

Douglas Hofstadter, "Fluid Concepts and Creative Analogies", Chapter 1: "To seek whence cometh a sequence".
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

T. D. Noe, Table of n, a(n) for n = 1..10000
F. M. Dekking, On the structure of self-generating sequences, Seminar on Number Theory, 1980-1981 (Talence, 1980-1981), Exp. No. 31, 6 pp., Univ. Bordeaux I, Talence, 1981. Math. Rev. 83e:10075.
D. R. Hofstadter, Eta-Lore [Cached copy, with permission]
D. R. Hofstadter, Pi-Mu Sequences [Cached copy, with permission]
D. R. Hofstadter and N. J. A. Sloane, Correspondence, 1977 and 1991
Clark Kimberling, Problem 6281, Amer. Math. Monthly 86 (1979), no. 9, 793.
N. J. A. Sloane, Families of Essentially Identical Sequences, Mar 24 2021 (Includes this sequence)

Cf. A006338. Exchanging 1's and 2's gives A080763. Essentially same as A004641 + 1.
Cf. A049472.
The following sequences are all essentially the same, in the sense that they are simple transformations of each other, with A003151 as the parent: A003151, A001951, A001952, A003152, A006337, A080763, A082844 (conjectured), A097509, A159684, A188037, A245219 (conjectured), A276862. - N. J. A. Sloane, Mar 09 2021
Cf. A245222 (an analog with sqrt(3) instead of sqrt(2)).

a006337 n = a006337_list !! (n-1)
a006337_list = f [1] where
   f xs = ys ++ f ys where
          ys = concatMap (\z -> if z == 1 then [1,2] else [1,1,2]) xs
-- Reinhard Zumkeller, May 06 2012

Digits := 100; sq2 := sqrt(2.); A006337 := n->floor((n+1)*sq2)-floor(n*sq2);

Flatten[ Table[ Nest[ Flatten[ # /. {1 -> {1, 2}, 2 -> {1, 1, 2}}] &, {1}, n], {n, 5}]] (* Robert G. Wilson v, May 06 2005 *)
Differences[ Table[ Floor[ n*Sqrt[2]], {n, 1, 106}]] (* Jean-François Alcover, Apr 06 2012 *)

a(n)=sqrt(2)*(n+1)\1-sqrt(2)*n\1 \\ Charles R Greathouse IV, Apr 06 2012

a(n)=sqrtint(2*n^2+4*n+2)-sqrtint(2*n^2) \\ Charles R Greathouse IV, Apr 06 2012

from math import isqrt
def A006337(n): return -isqrt(m:=n*n<<1)+isqrt(m+(n<<2)+2) # Chai Wah Wu, Aug 03 2022

Let S(0) = 1; obtain S(k) from S(k-1) by applying 1 -> 12, 2 -> 112; sequence is S(0), S(1), S(2), ... - Matthew Vandermast, Mar 25 2003
a(A003152(n)) = 1 and a(A003151(n)) = 2. - Philippe Deléham, May 29 2006
a(n) = A159684(n-1) + 1. - Filip Zaludek, Oct 28 2016

A096270 Fixed point of the morphism 0->01, 1->011.

Original entry on oeis.org

0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0

Offset: 0

N. J. A. Sloane, Jun 22 2004

This is another version of the Fibonacci word A005614.
(With offset 1) for k>0, a(ceiling(k*phi^2))=0 and a(floor(k*phi^2))=1 where phi=(1+sqrt(5))/2 is the Golden ratio. - Benoit Cloitre, Apr 01 2006
(With offset 1) for n>1 a(A000045(n)) = (1-(-1)^n)/2.
Equals the Fibonacci word A005614 with an initial zero.
Also the Sturmian word of slope phi (cf. A144595). - N. J. A. Sloane, Jan 13 2009
More precisely: (a(n)) is the inhomogeneous Sturmian word of slope phi-1 and intercept 0: a(n) = floor((n+1)*(phi-1)) - floor(n*(phi-1)), n >= 0. - Michel Dekking, May 21 2018
The ratio of number of 1's to number of 0's tends to the golden ratio (1+sqrt(5))/2 = 1.618... - Zak Seidov, Feb 15 2012

J.-P. Allouche and J. Shallit, Automatic Sequences, Cambridge Univ. Press, 2003.

A.H.M. Smeets, Table of n, a(n) for n = 0..20000
Scott Balchin and Dan Rust, Computations for Symbolic Substitutions, Journal of Integer Sequences, Vol. 20 (2017), Article 17.4.1.
J-P. Borel and François Laubie, Construction de mots de Christoffel, Comptes rendus de l'Académie des sciences. Série 1, Mathématique 313.8 (1991): 483-485.
N. J. A. Sloane, Families of Essentially Identical Sequences, Mar 24 2021 (Includes this sequence)
Richard Southwell and Jianwei Huang, Complex Networks from Simple Rewrite Systems, arXiv preprint arXiv:1205.0596 [cs.SI], 2012.
Index entries for sequences that are fixed points of mappings

Cf. A003849, A096268, A001519. See A005614, A114986 for other versions.

The following sequences are all essentially the same, in the sense that they are simple transformations of each other, with A000201 as the parent: A000201, A001030, A001468, A001950, A003622, A003842, A003849, A004641, A005614, A014675, A022342, A088462, A096270, A114986, A124841. - N. J. A. Sloane, Mar 11 2021

[-1+Floor(n*(1+Sqrt(5))/2)-Floor((n-1)*(1+Sqrt(5))/2): n in [1..100]]; // Wesley Ivan Hurt, Aug 29 2022

Nest[ Function[l, {Flatten[(l /. {0 -> {0, 1}, 1 -> {0, 1, 1}})]}], {0}, 6] (* Robert G. Wilson v, Feb 04 2005 *)

a(n)=-1+floor(n*(1+sqrt(5))/2)-floor((n-1)*(1+sqrt(5))/2) \\ Benoit Cloitre, Apr 01 2006

from math import isqrt
def A096270(n): return (n+1+isqrt(5*(n+1)**2)>>1)-(n+isqrt(5*n**2)>>1)>>1 # Chai Wah Wu, Aug 29 2022

Conjecture: a(n) is given recursively by a(1)=0 and, for n>1, by a(n)=1 if n=F(2k+1) and a(n)=a(n-F(2k+1)) otherwise, where F(2k+1) is the largest odd-indexed Fibonacci number smaller than or equal to n. (This has been confirmed for more than nine million terms.) The odd-indexed bisection of the Fibonacci numbers (A001519) is {1, 2, 5, 13, 34, 89, ...}. So by the conjecture, we would expect that a(30) = a(30-13) = a(17) = a(17-13) = a(4) = a(4-2) = a(2) = 1, which is in fact correct. - John W. Layman, Jun 29 2004
From Michel Dekking, Apr 13 2016: (Start)
Proof of the above conjecture:
Let g be the morphism above: g(0)=01, g(1)=011. Then g^n(0) has length F(2n+1), and (a(n)) starts with g^n(0) for all n>0. Obviously g^n(0) ends in 1 for all n, proving the first part of the conjecture.
We extend the semigroup of words with letters 0 and 1 to the free group, adding the inverses 0*:=0^{-1} and 1*:=1^{-1}. Easy observation: for any word w one has g(w1)= g(w0)1. We claim that for all n>1 one has g^n(0)=u(n)v(n)v(n)0*1, where u(n)=g(u(n-1))0 and v(n)=0*g(v(n-1))0. The recursion starts with u(2)=0, v(2)=10. Indeed: g^2(0)=01011=u(2)v(2)v(2)0*1. Induction step:
  g^{n+1}(0)=g(g^n(0))= g(u(n)v(n)v(n)0*1)= g(u(n)v(n)v(n))1= g(u(n))00*g(v(n))00*g(v(n))00*1=u(n+1)v(n+1)v(n+1)0*1.
Since v(n) has length F(2n-1), which is the largest odd-indexed Fibonacci number smaller than or equal to m for all m between F(2n-1) and F(2n+1), the claim proves the second part of the conjecture. (End)
(With offset 1) a(n) = -1 + floor(n*phi) - floor((n-1)*phi) where phi=(1+sqrt(5))/2 so a(n) = -1 + A082389(n). - Benoit Cloitre, Apr 01 2006

More terms from John W. Layman, Jun 29 2004

A039649 a(n) = phi(n)+1.

Original entry on oeis.org

2, 2, 3, 3, 5, 3, 7, 5, 7, 5, 11, 5, 13, 7, 9, 9, 17, 7, 19, 9, 13, 11, 23, 9, 21, 13, 19, 13, 29, 9, 31, 17, 21, 17, 25, 13, 37, 19, 25, 17, 41, 13, 43, 21, 25, 23, 47, 17, 43, 21, 33, 25, 53, 19, 41, 25, 37, 29, 59, 17, 61, 31, 37, 33, 49, 21, 67, 33, 45, 25, 71, 25, 73, 37, 41

Offset: 1

David W. Wilson

a(p) = p for p prime.
Records give A000040. - Omar E. Pol, Jul 10 2014
Which n are divisible by phi(n)+1? See A085118 for a possible answer and references. - Peter Munn, Jun 03 2021

Vincenzo Librandi, Table of n, a(n) for n = 1..10000
N. J. A. Sloane, Families of Essentially Identical Sequences, Mar 24 2021 (Includes this sequence)

Cf. A000010, A039650, A039651, A039652, A039653, A039654, A039655, A039656, A085118.

a039649 = (+ 1) . a000010  -- Reinhard Zumkeller, Oct 07 2015

[EulerPhi(n)+1: n in [1..100]]; // Vincenzo Librandi, Aug 13 2013

Table[EulerPhi[n] + 1, {n, 100}] (* Vincenzo Librandi, Aug 13 2013 *)

a(n)=eulerphi(n)+1 \\ Charles R Greathouse IV, Mar 04 2017

a(n) = A000010(n) + 1.
a(n) <= n for n > 1.
G.f.: x/(1 - x) + Sum_{k>=1} mu(k)*x^k/(1 - x^k)^2. - Ilya Gutkovskiy, Mar 16 2017

Edited by Charles R Greathouse IV, Mar 18 2010.

A001468 There are a(n) 2's between successive 1's.

Original entry on oeis.org

1, 2, 1, 2, 2, 1, 2, 1, 2, 2, 1, 2, 2, 1, 2, 1, 2, 2, 1, 2, 1, 2, 2, 1, 2, 2, 1, 2, 1, 2, 2, 1, 2, 2, 1, 2, 1, 2, 2, 1, 2, 1, 2, 2, 1, 2, 2, 1, 2, 1, 2, 2, 1, 2, 1, 2, 2, 1, 2, 2, 1, 2, 1, 2, 2, 1, 2, 2, 1, 2, 1, 2, 2, 1, 2, 1, 2, 2, 1, 2, 2, 1, 2, 1, 2, 2, 1, 2, 2, 1, 2, 1, 2

Offset: 0

N. J. A. Sloane

The Fibonacci word on the alphabet {2,1}, with an extra 1 in front. - Michel Dekking, Nov 26 2018
Start with 1, apply 1->12, 2->122, take limit. - Philippe Deléham, Sep 23 2005
Also number of occurrences of n in Hofstadter G-sequence (A005206) and in A019446. - Reinhard Zumkeller, Feb 02 2012, Aug 07 2011
A block-fractal sequence: every block occurs infinitely many times.  Also a reverse block-fractal sequence.  See A280511. - Clark Kimberling, Jan 06 2017

D. Gault and M. Clint, "Curiouser and curiouser" said Alice. Further reflections on an interesting recursive function, Internat. J. Computer Math., 26 (1988), 35-43. See Table 2.
D. R. Hofstadter, personal communication, Jul 15 1977.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Reinhard Zumkeller, Table of n, a(n) for n = 0..1000
M. Bunder and K. Tognetti, On the self matching properties of [j tau], Discrete Math., 241 (2001), 139-151.
D. Gault and M. Clint, "Curiouser and curiouser" said Alice. Further reflections on an interesting recursive function, Internat. J. Computer Math., 26 (1988), 35-43.
D. Gault and M. Clint, "Curiouser and curiouser said Alice. Further reflections on an interesting recursive function, Intern. J. Computer. Math., 26 (1988), 35-43. (Annotated scanned copy)
D. R. Hofstadter, Eta-Lore [Cached copy, with permission]
D. R. Hofstadter, Pi-Mu Sequences [Cached copy, with permission]
D. R. Hofstadter and N. J. A. Sloane, Correspondence, 1977 and 1991 [See DRH latter, p. 2, Eq. (2), the sequence marked A006336, which is now A001468].
J. V. Pennington and T. F. Mulcrone, Problem E1226, Amer. Math. Monthly, 64 (1957), 197-198.
Leon Recht, Martin Rosenbaum and E. P. Starke, Problem 4247, Amer. Math. Monthly, 55 (1948), 588-592.
N. J. A. Sloane, Handwritten notes on Self-Generating Sequences, 1970 (note that A1148 has now become A005282)
N. J. A. Sloane, Families of Essentially Identical Sequences, Mar 24 2021 (Includes this sequence)

Same as A014675 if initial 1 is deleted. Cf. A003849, A000201, A280511.

The following sequences are all essentially the same, in the sense that they are simple transformations of each other, with A000201 as the parent: A000201, A001030, A001468, A001950, A003622, A003842, A003849, A004641, A005614, A014675, A022342, A088462, A096270, A114986, A124841. - N. J. A. Sloane, Mar 11 2021

import Data.List (group)
a001468 n = a001468_list !! n
a001468_list = map length $ group a005206_list
-- Reinhard Zumkeller, Aug 07 2011

Digits := 100: t := evalf( (1+sqrt(5))/2); A001468 := n-> floor((n+1)*t)-floor(n*t);

Table[Floor[GoldenRatio*(n + 1)] - Floor[GoldenRatio*n], {n, 0, 80}] (* Joseph Biberstine (jrbibers(AT)indiana.edu), Aug 14 2006 *)
Nest[ Flatten[# /. {1 -> {1, 2}, 2 -> {1, 2, 2}}] &, {1}, 6] (* Robert G. Wilson v, May 20 2014 and corrected Apr 24 2017 following Clark Kimberling's email of Mar 22 2017 *)
SubstitutionSystem[{1->{1,2},2->{1,2,2}},{1},{6}][[1]] (* Harvey P. Dale, Jan 31 2022 *)

a=[1];for(i=1,30,a=concat([a,vector(a[i],j,2),1]));a \\ Or compute as A001468(n)=A201(n+1)-A201(n) with A201(n)=(n+sqrtint(5*n^2))\2, working for n>=0 although A000201 is defined for n>=1. - M. F. Hasler, Oct 13 2017

def A001468(length):
    a = [1]
    for i in range(length):
        for _ in range(a[i]):
            a.append(2)
        a.append(1)
        if len(a)>=length:
            break
    return a[:length] # Nicholas Stefan Georgescu, Jun 02 2022

from math import isqrt
def A001468(n): return (n+1+isqrt(m:=5*(n+1)**2)>>1)-(n+isqrt(m-10*n-5)>>1) # Chai Wah Wu, Aug 25 2022

a(n) = [(n+1) tau] - [n tau], tau = (1 + sqrt 5)/2 = A001622, [] = floor function.

a(n) = A000201(n+1) - A000201(n) = A022342(n+1) - A022342(n), n >= 1; i.e., the first term discarded, this yields the first differences of A000201 and A022342. - M. F. Hasler, Oct 13 2017

Rechecked by N. J. A. Sloane, Nov 07 2001

A062570 a(n) = phi(2*n).

Original entry on oeis.org

1, 2, 2, 4, 4, 4, 6, 8, 6, 8, 10, 8, 12, 12, 8, 16, 16, 12, 18, 16, 12, 20, 22, 16, 20, 24, 18, 24, 28, 16, 30, 32, 20, 32, 24, 24, 36, 36, 24, 32, 40, 24, 42, 40, 24, 44, 46, 32, 42, 40, 32, 48, 52, 36, 40, 48, 36, 56, 58, 32, 60, 60, 36, 64, 48, 40, 66, 64, 44, 48, 70, 48, 72

Offset: 1

Jason Earls, Jul 03 2001

a(n) is also the number of non-congruent solutions to x^2 - y^2 == 1 (mod n). - Yuval Dekel (dekelyuval(AT)hotmail.com), Sep 21 2003
a(n) is the size of a square companion matrix of the minimal cyclotomic polynomial of (-1)^(1/n). - Eric Desbiaux, Dec 08 2015
a(n) is the degree of the (2n)-th cyclotomic field Q(zeta_(2n)). Note that Q(zeta_n) = Q(zeta_(2n)) for odd n. - Jianing Song, May 17 2021
The number of integers k from 1 to n such that gcd(n,k) is a power of 2. - Amiram Eldar, May 18 2025

T. M. Apostol, Introduction to Analytic Number Theory, Springer-Verlag, 1976, p. 28.

Antti Karttunen, Table of n, a(n) for n = 1..65537 (first 1000 terms from Vincenzo Librandi)
N. J. A. Sloane, Families of Essentially Identical Sequences, Mar 24 2021 (Includes this sequence).
László Tóth, Counting solutions of quadratic congruences in several variables revisited, arXiv preprint arXiv:1404.4214 [math.NT], 2014.
László Tóth, Counting Solutions of Quadratic Congruences in Several Variables Revisited, J. Int. Seq. 17 (2014), Article 14.11.6.
Wikipedia, Ramanujan's sum.

Cf. A000010, A000034, A008683, A037225, A060968, A062803, A185199, A209229.
Column 1 of A129559, column 2 of A372673.
Row 1 of A379010.
Row sums of A129558 and of A129564.

[phi(2*n)$n=1..80]; # Muniru A Asiru, Mar 18 2019

Table[EulerPhi[2 n], {n, 80}] (* Vincenzo Librandi, Aug 23 2013 *)

PARI
```
a(n) = eulerphi(2*n)
```

from sympy import totient
def A062570(n): return totient(n) if n&1 else totient(n)<<1 # Chai Wah Wu, Aug 04 2024

[euler_phi(2*n) for n in range(1,74)] # Zerinvary Lajos, Jun 06 2009

a(n) = Sum_{d|n and d is odd} n/d*mu(d).
Multiplicative with a(2^e) = 2^e and a(p^e) = p^e-p^(e-1), p>2.
Dirichlet g.f.: zeta(s-1)/zeta(s)*2^s/(2^s-1). - Ralf Stephan, Jun 17 2007
a(n) = A000010(2*n).
a(n) = phi(n)*(1+((n+1) mod 2)). - Gary Detlefs, Jul 13 2011
a(n) = A173557(n)*b(n) where b(n) = 1, 2, 1, 4, 1, 2, 1, 8, 3, 2, 1, 4, 1, 2, ... is the multiplicative function defined by b(p^e) = p^(e-1) if p<>2 and b(2^e)=2^e. b(n) = n/A204455(n). - R. J. Mathar, Jul 02 2013
a(n) = -c_{2n}(n) where c_q(n) is Ramanujan's sum. - Michael Somos, Aug 23 2013
a(n) = A055034(2*n), for n >= 2. - Wolfdieter Lang, Nov 30 2013
O.g.f.: Sum_{n >= 1} mu(2*n-1)*x^(2*n-1)/(1 - x^(2*n-1))^2. - Peter Bala, Mar 17 2019
a(n) = A000010(4*n)/2, for n > = 1 (see Apostol, Theorem 2.5, (b), p. 28). - Wolfdieter Lang, Nov 17 2019
a(n) = n - Sum_{d|n, n/d odd, d < n} a(d). - Ilya Gutkovskiy, May 30 2020
Dirichlet convolution of A000010 and A209229. - Werner Schulte, Jan 17 2021
From Richard L. Ollerton, May 07 2021: (Start)
a(n) = Sum_{k=1..n} A209229(gcd(n,k)).
a(n) = Sum_{k=1..n} A209229(n/gcd(n,k))*phi(gcd(n,k))/phi(n/gcd(n,k)). (End)
Sum_{k=1..n} a(k) ~ c * n^2, where c = 4/Pi^2 = 0.405284... (A185199). - Amiram Eldar, Oct 22 2022
a(n) = A000034(n) * A000010(n). - Amiram Eldar, May 18 2025

Corrected by Vladeta Jovovic, Dec 04 2002

A290131 Number of regions in a regular drawing of the complete bipartite graph K_{n,n}.

Original entry on oeis.org

0, 2, 12, 40, 96, 204, 368, 634, 1012, 1544, 2236, 3186, 4360, 5898, 7764, 10022, 12712, 16026, 19844, 24448, 29708, 35756, 42604, 50602, 59496, 69650, 80940, 93600, 107540, 123316, 140428, 159642, 180632, 203618, 228556, 255822, 285080, 317326, 352020, 389498

Offset: 1

R. J. Mathar, Jul 20 2017

Chai Wah Wu, Table of n, a(n) for n = 1..10000
Martin Griffiths, Counting the regions in a regular drawing of K_{n,n}, J. Int. Seq. 13 (2010) # 10.8.5. See Lemma 2 and Table 1.
Stéphane Legendre, The Number of Crossings in a Regular Drawing of the Complete Bipartite Graph, J. Integer Seqs., Vol. 12, 2009.
N. J. A. Sloane, Families of Essentially Identical Sequences, Mar 24 2021 (Includes this sequence)
Eric Weisstein's World of Mathematics, Complete Bipartite Graph

Cf. A115004, A159065, A290132, A331754.
For K_n see A007569, A007678, A135563.
The following eight sequences are all essentially the same. The simplest is A115004(n), which we denote by z(n). Then A088658(n) = 4*z(n-1); A114043(n) = 2*z(n-1)+2*n^2-2*n+1; A114146(n) = 2*A114043(n); A115005(n) = z(n-1)+n*(n-1); A141255(n) = 2*z(n-1)+2*n*(n-1); A290131(n) = z(n-1)+(n-1)^2; A306302(n) = z(n)+n^2+2*n. - N. J. A. Sloane, Feb 04 2020

A290131 := proc(n)
    A115004(n-1)+(n-1)^2 ;
end proc:
seq(A290131(n),n=1..30) ;

z[n_] := Sum[(n - i + 1)(n - j + 1) Boole[GCD[i, j] == 1], {i, n}, {j, n}];
a[n_] := z[n - 1] + (n - 1)^2;
Array[a, 40] (* Jean-François Alcover, Mar 24 2020 *)

from math import gcd
def a115004(n):
    r=0
    for a in range(1, n + 1):
        for b in range(1, n + 1):
            if gcd(a, b)==1:r+=(n + 1 - a)*(n + 1 - b)
    return r
def a(n): return a115004(n - 1) + (n - 1)**2
print([a(n) for n in range(1, 51)]) # Indranil Ghosh, Jul 20 2017, after Maple code

from sympy import totient
def A290131(n): return 2*(n-1)**2 + sum(totient(i)*(n-i)*(2*n-i) for i in range(2,n)) # Chai Wah Wu, Aug 16 2021

a(n) = A115004(n-1) + (n-1)^2.

a(n) = 2*(n-1)^2 + Sum_{i=2..n-1} (n-i)*(2n-i)*phi(i). - Chai Wah Wu, Aug 16 2021

A331755 Number of vertices in a regular drawing of the complete bipartite graph K_{n,n}.

Original entry on oeis.org

2, 5, 13, 35, 75, 159, 275, 477, 755, 1163, 1659, 2373, 3243, 4429, 5799, 7489, 9467, 11981, 14791, 18275, 22215, 26815, 31847, 37861, 44499, 52213, 60543, 70011, 80347, 92263, 105003, 119557, 135327, 152773, 171275, 191721, 213547, 237953

Offset: 1

N. J. A. Sloane, Feb 02 2020

nonn

N. J. A. Sloane, Table of n, a(n) for n = 1..1000
Lars Blomberg, Scott R. Shannon, N. J. A. Sloane, Graphical Enumeration and Stained Glass Windows, 1: Rectangular Grids, (2020). Also arXiv:2009.07918.
M. Griffiths, Counting the regions in a regular drawing of K_{n,n}, J. Int. Seq. 13 (2010) # 10.8.5, Lemma 2.
S. Legendre, The Number of Crossings in a Regular Drawing of the Complete Bipartite Graph, J. Integer Seqs., Vol. 12, 2009.
Scott R. Shannon, Images of vertices for n=2.
Scott R. Shannon, Images of vertices for n=3.
Scott R. Shannon, Images of vertices for n=4.
Scott R. Shannon, Images of vertices for n=5.
Scott R. Shannon, Images of vertices for n=6
Scott R. Shannon, Images of vertices for n=7
Scott R. Shannon, Images of vertices for n=8
Scott R. Shannon, Images of vertices for n=9
Scott R. Shannon, Images of vertices for n=10.
Scott R. Shannon, Images of vertices for n=12.
Scott R. Shannon, Images of vertices for n=15.
Eric Weisstein's World of Mathematics, Complete Bipartite Graph
Index entries for sequences related to stained glass windows

Cf. A290131 (regions), A290132 (edges), A333274 (polygons per vertex), A333276, A159065.

For K_n see A007569, A007678, A135563.

# Maple code from N. J. A. Sloane, Jul 16 2020
V106i := proc(n) local ans,a,b; ans:=0;
for a from 1 to n-1 do for b from 1 to n-1 do
if igcd(a,b)=1 then ans:=ans + (n-a)*(n-b); fi; od: od: ans; end; # A115004
V106ii := proc(n) local ans,a,b; ans:=0;
for a from 1 to floor(n/2) do for b from 1 to floor(n/2) do
if igcd(a,b)=1 then ans:=ans + (n-2*a)*(n-2*b); fi; od: od: ans; end; # A331761
A331755 := n -> 2*(n+1) + V106i(n+1) - V106ii(n+1);

a[n_]:=Module[{x,y,s1=0,s2=0}, For[x=1, x<=n-1, x++, For[y=1, y<=n-1, y++, If[GCD[x,y]==1,s1+=(n-x)*(n-y); If[2*x<=n-1&&2*y<=n-1,s2+=(n-2*x)*(n-2*y)]]]]; s1-s2]; Table[a[n]+ 2 n, {n, 1, 40}] (* Vincenzo Librandi, Feb 04 2020 *)

a(n) = A290132(n) - A290131(n) + 1.
a(n) = A159065(n) + 2*n.
This is column 1 of A331453.
a(n) = (9/(8*Pi^2))*n^4 + O(n^3 log(n)). Asymptotic to (9/(2*Pi^2))*A000537(n-1). [Stéphane Legendre, see A159065.]

cp's OEIS Frontend

A014675 The infinite Fibonacci word (start with 1, apply 1->2, 2->21, take limit).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Python

Formula

Extensions

A000057 Primes dividing all Fibonacci sequences.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

PARI

PARI

PARI

Extensions

A003151 Beatty sequence for 1+sqrt(2); a(n) = floor(n*(1+sqrt(2))).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula

A006337 An "eta-sequence": a(n) = floor( (n+1)*sqrt(2) ) - floor( n*sqrt(2) ).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

Python

Formula

A096270 Fixed point of the morphism 0->01, 1->011.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Python

Formula

Extensions

A039649 a(n) = phi(n)+1.

Views

Author

Keywords

Comments

A006337 An "eta-sequence": a(n) = floor( (n+1)sqrt(2) ) - floor( nsqrt(2) ).