Search: a001468 -id:a001468
|
| |
| |
|
|
|
2, 2, 5, 5, 5, 5, 5, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 34, 34, 34, 34, 34, 34, 34, 34, 34, 34, 34, 34, 34, 34, 34, 34, 34, 34, 34, 34, 34, 34, 34, 34, 34, 34, 34, 34, 34, 34, 34, 34, 34, 34, 89, 89, 89, 89, 89, 89, 89, 89, 89, 89, 89, 89
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,1
|
|
|
COMMENTS
|
The index sequence (a(n)) of a block-fractal sequence (s(n)) is defined here by a(n) = least k > 0 such that (s(k), s(k+1), ..., s(k+n)) = (s(0), s(1), ..., s(n)). Following are definitions of block-fractal, reverse block-fractal, complementary block-fractal, and reverse complementary block-fractal, as pertain to any sequence s = (s(n)): s is block-fractal if every finite block s* of consecutive terms in s occurs more than once in s, and reverse block-fractal if reversal(s*) occurs in s; a zero-one sequence s is complement block-fractal if 1-s* occurs in s for every finite block S* of consecutive terms in s, and reverse complement block-fractal if reverse(1-s*) occurs in s.
Clearly each of the 4 containment conditions holds for all blocks s* if it holds for every initial block in s. Moreover, in all 4 cases, such a sequence s* occurs infinitely many times in s. This proper containment of infinitely many identical copies is comparable to proper containment of similar images in geometric fractals, hence the use of the word "fractal" for sequences.
The standard term for "block-fractal sequence" in the combinatorics on words literature is "recurrent sequence". The standard term for "reverse block-fractal" is "mirror-invariant". - Jeffrey Shallit, May 28 2023
|
|
|
LINKS
|
|
|
|
FORMULA
|
Concatenate F(2n+1) copies of F(2n+1), for n >= 1, where F = A000045, the Fibonacci numbers.
|
|
|
EXAMPLE
|
A001468 = (1,2,1,2,2,1,2,1,2,2,1,2,2,...) = (s(0), s(1), ... ).
(initial block #1) = (1) first repeats at s(2), so that a(1) = 2;
(initial block #2) = (1,2) first repeats at s(2), so that a(2) = 2;
(initial block #3) = (1,2,1) first repeats at s(5), so that a(3) = 5.
|
|
|
MATHEMATICA
|
r = GoldenRatio; seq = Table[Floor[(n + 1) r] - Floor[n r], {n, 0, 300}] (*A001468*)
seq = StringJoin[Map[ToString, seq]]
u = -1 + Most[Flatten[Rest[Reap[NestWhile[# + 1 &, 1, Sow[First[Last[StringPosition[seq, StringTake[seq, #], 2]]]] >
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,easy
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
| |
|
|
A280513
|
|
Index sequence of the reverse block-fractal sequence A001468.
|
|
+20
3
|
|
|
|
1, 2, 1, 5, 4, 3, 2, 1, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 34, 33, 32, 31, 30, 29, 28, 27, 26, 25, 24, 23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 89, 88, 87, 86, 85, 84, 83, 82, 81, 80, 79, 78, 77, 76, 75, 74
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,2
|
|
|
COMMENTS
|
The sequence is the concatenation of blocks, the n-th of which, for n >= 1, consists of the integers from F(2n+1) down to F(2) = 1, where F = A000045, the Fibonacci numbers. See A280511 for the definition of reverse block-fractal sequence. The index sequence (a(n)) of a reverse block-fractal sequence (s(n)) is defined here by a(n) = least k > 0 such that (s(k), s(k+1), ..., s(k+n)) = (s(n), s(n-1), ..., s(1)).
Let W be the Fibonacci word A096270. Then a(n) = least k such that the reversal of the first n-block in W occurs in W beginning at the k-th term. Since (a(n)) is unbounded, the reversal of every block in W occurs infinitely many times in W. - Clark Kimberling, Dec 17 2020
|
|
|
LINKS
|
|
|
|
EXAMPLE
|
A001468 = (1,2,1,2,2,1,2,1,2,2,1,2,2,...) = (s(1), s(2), ... ).
(init. block #1) = (1); reversal (1) first occurs at s(1), so a(1) = 1;
(init. block #2) = (1,2); rev. (2,1) first occurs at s(2), so a(2) = 2;
(init. block #3) = (1,2,1); rev. (1,2,1) first occurs at s(1), so a(3) = 1;
(init. block #4) = (1,2,1,2); rev. (2,1,2,1) first occurs at s(5), so a(4) = 5.
|
|
|
MATHEMATICA
|
r = GoldenRatio; t = Table[Floor[(n + 1) r] - Floor[n*r], {n, 0, 420}]
u = StringJoin[Map[ToString, t]]; breverse[seq_] :=
Flatten[Last[Reap[NestWhile[# + 1 &, 1, (StringLength[
str = StringTake[seq, Min[StringLength[seq], #]]] == # && ! (Sow[
StringPosition[seq, StringReverse[str], 1][[1]][[1]]]) === {}) &]]]];
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,easy
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
| |
| |
|
|
|
1, -1, 1, 0, -1, 1, -1, 1, 0, -1, 1, 0, -1, 1, -1, 1, 0, -1, 1, -1, 1, 0, -1, 1, 0, -1, 1, -1, 1, 0, -1, 1, 0, -1, 1, -1, 1, 0, -1, 1, -1, 1, 0, -1, 1, 0, -1, 1, -1, 1, 0, -1, 1, -1, 1, 0, -1, 1, 0, -1, 1, -1, 1, 0, -1, 1, 0, -1, 1, -1, 1, 0, -1, 1, -1, 1, 0, -1, 1, 0, -1, 1, -1, 1, 0, -1, 1, 0, -1, 1, -1, 1
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,1
|
|
|
COMMENTS
|
c(n):=a(n-1), n >= 1, is -1 if n is a Wythoff B-number from A001950, it is 0 if n=A(B(m)+1) for some m >= 1, with A(k):=A000201(k) (Wythoff A-numbers) and it is +1 if n=A(A(m)+1)=B(m)+1 for some m >= 0, with B(0):=0. - Wolfdieter Lang, Oct 13 2006
This sequence is a symbolic sequence as discussed in the paper "Morphisms, Symbolic Sequences, and Their Standard Forms". It can be derived directly from the 2-block morphism induced by the morphism generating A001468. Since A001468 is the Fibonacci word A003849, but on the alphabet {2,1}, with an extra 1 in front, this 2-block morphism has 3-symbol Fibonacci as a fixed point: A270788. The 2-blocks in A001468 are 12, 21, and 22, yielding the differences a(n) = 1, a(n) = -1, and a(n) = 0. In 3-symbol Fibonacci these correspond to the letters 2, 1, and 3. Expressing this coding with pi given by pi(1)=-1, pi(2)=1, pi(3)=0, we obtain the formula below. Wolfdieter Lang's Wythoff description of (a(n)) follows from the corresponding Wythoff description in A270788. - Michel Dekking, Dec 30 2019
|
|
|
LINKS
|
|
|
|
FORMULA
|
abs(a(n)) = floor(f*ceiling(n/f)) - ceiling(f*floor(n/f)) where f=phi=(1+sqrt(5))/2; for n > 1, abs(a(n)) = A005713(n-1). - Benoit Cloitre, Apr 21 2003
G.f. equals the continued fraction: A(x) = [0;1, 1/x, 1/x, 1/x^2, 1/x^3, 1/x^5, 1/x^8, ..., 1/x^Fibonacci(n), ...]. - Paul D. Hanna, Dec 17 2004
a(n) = b(n) - b(n-1) with b(n):=A005614(n), n >= 1.
a(n) = pi(A270788(n)), n >= 1, where pi is the letter-to-letter map pi(1)=-1, pi(2)=1, pi(3)=0. - Michel Dekking, Dec 30 2019
|
|
|
PROG
|
(Python)
from math import isqrt
def A014677(n): return (n+isqrt(m:=5*(n+2)**2)>>1)-(n+1+isqrt(m-10*n-15)&-2)+(n+isqrt(m-20*n-20)>>1)+1 # Chai Wah Wu, Aug 25 2022
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
sign
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
| |
|
|
A000201
|
|
Lower Wythoff sequence (a Beatty sequence): a(n) = floor(n*phi), where phi = (1+sqrt(5))/2 = A001622.
(Formerly M2322 N0917)
|
|
+10
310
|
|
|
|
1, 3, 4, 6, 8, 9, 11, 12, 14, 16, 17, 19, 21, 22, 24, 25, 27, 29, 30, 32, 33, 35, 37, 38, 40, 42, 43, 45, 46, 48, 50, 51, 53, 55, 56, 58, 59, 61, 63, 64, 66, 67, 69, 71, 72, 74, 76, 77, 79, 80, 82, 84, 85, 87, 88, 90, 92, 93, 95, 97, 98, 100, 101, 103, 105, 106, 108, 110
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,2
|
|
|
COMMENTS
|
This is the unique sequence a satisfying a'(n)=a(a(n))+1 for all n in the set N of natural numbers, where a' denotes the ordered complement (in N) of a. - Clark Kimberling, Feb 17 2003
This sequence and A001950 may be defined as follows. Consider the maps a -> ab, b -> a, starting from a(1) = a; then A000201 gives the indices of a, A001950 gives the indices of b. The sequence of letters in the infinite word begins a, b, a, a, b, a, b, a, a, b, a, ... Setting a = 0, b = 1 gives A003849 (offset 0); setting a = 1, b = 0 gives A005614 (offset 0). - Philippe Deléham, Feb 20 2004
These are the numbers whose lazy Fibonacci representation (see A095791) includes 1; the complementary sequence (the upper Wythoff sequence, A001950) are the numbers whose lazy Fibonacci representation includes 2 but not 1.
a(n) is the unique monotonic sequence satisfying a(1)=1 and the condition "if n is in the sequence then n+(rank of n) is not in the sequence" (e.g. a(4)=6 so 6+4=10 and 10 is not in the sequence) - Benoit Cloitre, Mar 31 2006
Write A for A000201 and B for A001950 (the upper Wythoff sequence, complement of A). Then the composite sequences AA, AB, BA, BB, AAA, AAB,...,BBB,... appear in many complementary equations having solution A000201 (or equivalently, A001950). Typical complementary equations: AB=A+B (=A003623), BB=A+2B (=A101864), BBB=3A+5B (=A134864). - Clark Kimberling, Nov 14 2007
The lower Wythoff sequence also can be constructed by playing the so-called Mancala-game: n piles of total d(n) chips are standing in a row. The piles are numbered from left to right by 1, 2, 3, ... . The number of chips in a pile at the beginning of the game is equal to the number of the pile. One step of the game is described as follows: Distribute the pile on the very left one by one to the piles right of it. If chips are remaining, build piles out of one chip subsequently to the right. After f(n) steps the game ends in a constant row of piles. The lower Wythoff sequence is also given by n -> f(n). - Roland Schroeder (florola(AT)gmx.de), Jun 19 2010
With the exception of the first term, a(n) gives the number of iterations required to reverse the list {1,2,3,...,n} when using the mapping defined as follows: remove the first term of the list, z(1), and add 1 to each of the next z(1) terms (appending 1's if necessary) to get a new list. See A183110 where this mapping is used and other references given. This appears to be essentially the Mancala-type game interpretation given by R. Schroeder above. - John W. Layman, Feb 03 2011
Numbers k such that {k*phi} > phi^(-2), where {} denotes the fractional part.
Proof: Write m = floor(k*phi).
If {k*phi} > phi^(-2), take s = m-k+1. From m < k*phi < m+1 we have k < (m-k+1)*phi < k + phi, so floor(s*phi) = k or k+1. If floor(s*phi) = k+1, then (see A003622) floor((k+1)*phi) = floor(floor(s*phi)*phi) = floor(s*phi^2)-1 = s+floor(s*phi)-1 = m+1, but actually we have (k+1)*phi > m+phi+phi^(-2) = m+2, a contradiction. Hence floor(s*phi) = k.
If floor(s*phi) = k, suppose otherwise that k*phi - m <= phi^(-2), then m < (k+1)*phi <= m+2, so floor((k+1)*phi) = m+1. Suppose that A035513(p,q) = k for p,q >= 1, then A035513(p,q+1) = floor((k+1)*phi) - 1 = m = A035513(s,1). But it is impossible for one number (m) to occur twice in A035513. (End)
The formula from Jianing Song above is a direct consequence of an old result by Carlitz et al. (1972). Their Theorem 11 states that (a(n)) consists of the numbers k such that {k*phi^(-2)} < phi^(-1). One has {k*phi^(-2)} = {k*(2-phi)} = {-k*phi}. Using that 1-phi^(-1) = phi^(-2), the Jianing Song formula follows. - Michel Dekking, Oct 14 2023
|
|
|
REFERENCES
|
Eric Friedman, Scott M. Garrabrant, Ilona K. Phipps-Morgan, A. S. Landsberg and Urban Larsson, Geometric analysis of a generalized Wythoff game, in Games of no Chance 5, MSRI publ. Cambridge University Press, date?
M. Gardner, Penrose Tiles to Trapdoor Ciphers, W. H. Freeman, 1989; see p. 107.
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).
I. M. Yaglom, Two games with matchsticks, pp. 1-7 of Qvant Selecta: Combinatorics I, Amer Math. Soc., 2001.
|
|
|
LINKS
|
L. Carlitz, Richard Scoville, and V. E. Hoggatt, Jr., Fibonacci representations, Fib. Quart., Vol. 10, No. 1 (1972), pp. 1-28.
Eric Duchene, Aviezri S. Fraenkel, Vladimir Gurvich, Nhan Bao Ho, Clark Kimberling, and Urban Larsson, Wythoff Wisdom, 43 pages, no date, unpublished.
Eric Duchene, Aviezri S. Fraenkel, Vladimir Gurvich, Nhan Bao Ho, Clark Kimberling, and Urban Larsson, Wythoff Wisdom, unpublished, no date [Cached copy, with permission]
A. S. Fraenkel, Ratwyt, December 28 2011.
Clark Kimberling, Problem Proposals, The Fibonacci Quarterly, vol. 52 #5, 2015, p5-14.
Wolfdieter Lang, The Wythoff and the Zeckendorf representations of numbers are equivalent, in G. E. Bergum et al. (edts.) Application of Fibonacci numbers vol. 6, Kluwer, Dordrecht, 1996, pp. 319-337.[See A317208 for a link.]
D. J. Newman, Problem 3117, Amer. Math. Monthly, 34 (1927), 158-159.
D. J. Newman, Problem 5252, Amer. Math. Monthly, 72 (1965), 1144-1145.
|
|
|
FORMULA
|
Zeckendorf expansion of n (cf. A035517) ends with an even number of 0's.
Other properties: a(1)=1; for n>1, a(n) is taken to be the smallest integer greater than a(n-1) which is consistent with the condition "n is in the sequence if and only if a(n)+1 is not in the sequence".
a(1) = 1; for n>0, a(n+1) = a(n)+1 if n is not in the sequence, a(n+1) = a(n)+2 if n is in the sequence.
a(a(n)) = floor(n*phi^2) - 1 = A003622(n).
{a(k)} union {a(k)+1} = {1, 2, 3, 4, ...}. Hence a(1) = 1; for n>1, a(a(n)) = a(a(n)-1)+2, a(a(n)+1) = a(a(n))+1. - Benoit Cloitre, Mar 08 2003
{a(n)} is a solution to the recurrence a(a(n)+n) = 2*a(n)+n, a(1)=1 (see Barbeau et al.).
a(Fibonacci(r-1)+j) = Fibonacci(r)+a(j) for 0 < j <= Fibonacci(r-2); 2 < r. - Paul Weisenhorn, Aug 18 2012
|
|
|
EXAMPLE
|
From Roland Schroeder (florola(AT)gmx.de), Jul 13 2010: (Start)
Example for n = 5; a(5) = 8;
(Start: [1,2,3,4,5]; 8 steps until [5,4,3,2,1]):
[1,2,3,4,5]; [3,3,4,5]; [4,5,6]; [6,7,1,1]; [8,2,2,1,1,1]: [3,3,2,2,2,1,1,1]; [4,3,3,2,1,1,1]; [4,4,3,2,1,1]; [5,4,3,2,1]. (End)
|
|
|
MAPLE
|
Digits := 100; t := evalf((1+sqrt(5))/2); A000201 := n->floor(t*n);
|
|
|
MATHEMATICA
|
Table[Floor[N[n*(1+Sqrt[5])/2]], {n, 1, 75}]
|
|
|
PROG
|
(PARI) a(n)=floor(n*(sqrt(5)+1)/2)
(Maxima) makelist(floor(n*(1+sqrt(5))/2), n, 1, 60); /* Martin Ettl, Oct 17 2012 */
(Haskell)
a000201 n = a000201_list !! (n-1)
a000201_list = f [1..] [1..] where
f (x:xs) (y:ys) = y : f xs (delete (x + y) ys)
(Python)
def aupton(terms):
alst, aset = [None, 1], {1}
for n in range(1, terms):
an = alst[n] + (1 if n not in aset else 2)
alst.append(an); aset.add(an)
return alst[1:]
(Python)
from math import isqrt
|
|
|
CROSSREFS
|
A185615 gives values n such that n divides A000201(n)^m for some integer m>0.
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
|
|
|
KEYWORD
|
nonn,easy,nice
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
| |
|
|
A001950
|
|
Upper Wythoff sequence (a Beatty sequence): a(n) = floor(n*phi^2), where phi = (1+sqrt(5))/2.
(Formerly M1332 N0509)
|
|
+10
251
|
|
|
|
2, 5, 7, 10, 13, 15, 18, 20, 23, 26, 28, 31, 34, 36, 39, 41, 44, 47, 49, 52, 54, 57, 60, 62, 65, 68, 70, 73, 75, 78, 81, 83, 86, 89, 91, 94, 96, 99, 102, 104, 107, 109, 112, 115, 117, 120, 123, 125, 128, 130, 133, 136, 138, 141, 143, 146, 149, 151, 154, 157
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,1
|
|
|
COMMENTS
|
Indices at which blocks (1;0) occur in infinite Fibonacci word; i.e., n such that A005614(n-2) = 0 and A005614(n-1) = 1. - Benoit Cloitre, Nov 15 2003
A000201 and this sequence may be defined as follows: Consider the maps a -> ab, b -> a, starting from a(1) = a; then A000201 gives the indices of a, A001950 gives the indices of b. The sequence of letters in the infinite word begins a, b, a, a, b, a, b, a, a, b, a, ... Setting a = 0, b = 1 gives A003849 (offset 0); setting a = 1, b = 0 gives A005614 (offset 0). - Philippe Deléham, Feb 20 2004
a(n) = n-th integer which is not equal to the floor of any multiple of phi, where phi = (1+sqrt(5))/2 = golden number. - Philippe LALLOUET (philip.lallouet(AT)wanadoo.fr), May 09 2007
Write A for A000201 and B for the present sequence (the upper Wythoff sequence, complement of A). Then the composite sequences AA, AB, BA, BB, AAA, AAB, ..., BBB, ... appear in many complementary equations having solution A000201 (or equivalently, the present sequence). Typical complementary equations: AB=A+B (=A003623), BB=A+2B (=A101864), BBB=3A+5B (=A134864). - Clark Kimberling, Nov 14 2007
Apart from the initial 0 in A090909, is this the same as that sequence? - Alec Mihailovs (alec(AT)mihailovs.com), Jul 23 2007
If we define a base-phi integer as a positive number whose representation in the golden ratio base consists only of nonnegative powers of phi, and if these base-phi integers are ordered in increasing order (beginning 1, phi, ...), then it appears that the difference between the n-th and (n-1)-th base-phi integer is phi-1 if and only if n belongs to this sequence, and the difference is 1 otherwise. Further, if each base-phi integer is written in linear form as a + b*phi (for example, phi^2 is written as 1 + phi), then it appears that there are exactly two base-phi integers with b=n if and only if n belongs to this sequence, and exactly three base-phi integers with b=n otherwise. - Geoffrey Caveney, Apr 17 2014
Numbers with an odd number of trailing zeros in their Zeckendorf representation (A014417). - Amiram Eldar, Feb 26 2021
|
|
|
REFERENCES
|
Claude Berge, Graphs and Hypergraphs, North-Holland, 1973; p. 324, Problem 2.
Eric Friedman, Scott M. Garrabrant, Ilona K. Phipps-Morgan, A. S. Landsberg and Urban Larsson, Geometric analysis of a generalized Wythoff game, in Games of no Chance 5, MSRI publ. Cambridge University Press, 2019.
Martin Gardner, Penrose Tiles to Trapdoor Ciphers, W. H. Freeman, 1989; see p. 107.
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).
I. M. Yaglom, Two games with matchsticks, pp. 1-7 of Qvant Selecta: Combinatorics I, Amer Math. Soc., 2001.
|
|
|
LINKS
|
Eric Duchene, Aviezri S. Fraenkel, Vladimir Gurvich, Nhan Bao Ho, Clark Kimberling, and Urban Larsson, Wythoff Wisdom, 43 pages, no date, unpublished.
Eric Duchene, Aviezri S. Fraenkel, Vladimir Gurvich, Nhan Bao Ho, Clark Kimberling, and Urban Larsson, Wythoff Wisdom, unpublished, no date [Cached copy, with permission]
Aviezri S. Fraenkel, The Raleigh game, INTEGERS: Electronic Journal of Combinatorial Number Theory 7.2 (2007): A13, 10 pages. See Table 1.
Aviezri S. Fraenkel, Ratwyt, December 28 2011.
D. J. Newman, Problem 5252, Amer. Math. Monthly, Vol. 72, No. 10 (1965), pp. 1144-1145.
|
|
|
FORMULA
|
a(n) = n + floor(n*phi). In general, floor(n*phi^m) = Fibonacci(m-1)*n + floor(Fibonacci(m)*n*phi). - Benoit Cloitre, Mar 18 2003
Append a 0 to the Zeckendorf expansion (cf. A035517) of n-th term of A000201.
If a'=A000201 is the ordered complement (in N) of {a(n)}, then a(Fib(r-2) + j) = Fib(r) + a(j) for 0 < j <= Fib(r-2), 3 < r; and a'(Fib(r-1) + j) = Fib(r) + a'(j) for 0 < j <= Fib(r-2), 2 < r. - Paul Weisenhorn, Aug 18 2012
With a(1)=2, a(2)=5, a'(1)=1, a'(2)=3 and 1 < k and a(k-1) < n <= a(k) one gets a(n)=3*n-k, a'(n)=2*n-k. - Paul Weisenhorn, Aug 21 2012
|
|
|
EXAMPLE
|
a(14) = floor(14*phi^2) = 36; a'(14) = floor(14*phi)=22;
with r=9 and j=1: a(13+1) = 34 + 2 = 36;
with r=8 and j=1: a'(13+1) = 21 + 1 = 22.
k=6 and a(5)=13 < n <= a(6)=15
a(14) = 3*14 - 6 = 36; a'(14) = 2*14 - 6 = 22;
a(15) = 3*15 - 6 = 39; a'(15) = 2*15 - 6 = 24. (End)
|
|
|
MAPLE
|
floor(n*(3+sqrt(5))/2) ;
end proc:
|
|
|
MATHEMATICA
|
Table[Floor[N[n*(1+Sqrt[5])^2/4]], {n, 1, 75}]
|
|
|
PROG
|
(PARI) a(n)=floor(n*(sqrt(5)+3)/2)
(Haskell)
(Magma) [Floor(n*((1+Sqrt(5))/2)^2): n in [1..80]]; // Vincenzo Librandi, Nov 19 2016
(Python)
from math import isqrt
|
|
|
CROSSREFS
|
a(n) = greatest k such that s(k) = n, where s = A026242.
First differences give (essentially) A076662.
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
|
|
|
KEYWORD
|
nonn,easy,nice,changed
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
| |
|
|
A003849
|
|
The infinite Fibonacci word (start with 0, apply 0->01, 1->0, take limit).
|
|
+10
209
|
|
|
|
0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,1
|
|
|
COMMENTS
|
A Sturmian word.
Define strings S(0)=0, S(1)=01, S(n)=S(n-1)S(n-2); iterate; sequence is S(infinity). If the initial 0 is omitted from S(n) for n>0, we obtain A288582(n+1).
Replace each run (1;1) with (1;0) in the infinite Fibonacci word A005614 (and add 0 as prefix) A005614 begins: 1,0,1,1,0,1,0,1,1,0,1,1,... changing runs (1,1) with (1,0) produces 1,0,0,1,0,1,0,0,1,0,0,1,... - Benoit Cloitre, Nov 10 2003
The fraction of 0's in the first n terms approaches 1/phi (see for example Allouche and Shallit). - N. J. A. Sloane, Sep 24 2007
The limiting mean and variance of the first n terms are 2-phi and 2*phi-3, respectively. - Clark Kimberling, Mar 12 2014, Aug 16 2018
Let S(n) be defined as above. Then this sequence is S(1) + Sum_{n=0..} S(n), where the addition of strings represents concatenation. - Isaac Saffold, May 03 2019
The word is a concatenation of three runs: 0, 1, and 00. The limiting proportions of these are respectively 1 - phi/2, 1/2, and (phi - 1)/2. The mean runlength is (phi + 1)/2. - Clark Kimberling, Dec 26 2010
a(n) is the number of the trailing 0's in the dual Zeckendorf representation of (n+1) (A104326).
The asymptotic density of the occurrences of k (0 or 1) is 1/phi^(k+1), where phi is the golden ratio (A001622).
The asymptotic mean of this sequence is 1/phi^2 (A132338). (End)
|
|
|
REFERENCES
|
J.-P. Allouche and J. Shallit, Automatic Sequences, Cambridge Univ. Press, 2003.
Jean Berstel, Fibonacci words—a survey, In The book of L, pp. 13-27. Springer Berlin Heidelberg, 1986.
J. C. Lagarias, Number Theory and Dynamical Systems, pp. 35-72 of S. A. Burr, ed., The Unreasonable Effectiveness of Number Theory, Proc. Sympos. Appl. Math., 46 (1992). Amer. Math. Soc. - see p. 64.
Wolfdieter Lang, The Wythoff and the Zeckendorf representations of numbers are equivalent, in G. E. Bergum et al. (edts.) Application of Fibonacci numbers vol. 6, Kluwer, Dordrecht, 1996, pp. 319-337. [See A317208 for a link.]
G. Melançon, Factorizing infinite words using Maple, MapleTech journal, vol. 4, no. 1, 1997, pp. 34-42, esp. p. 36.
Michel Rigo, Formal Languages, Automata and Numeration Systems, 2 vols., Wiley, 2014. Mentions this sequence - see "List of Sequences" in Vol. 2.
|
|
|
LINKS
|
A. G. M. Ahmed, AA Weaving, in Proceedings of Bridges 2013: Mathematics, Music, Art, Architecture, Culture.
Jean-Paul Allouche, Julien Cassaigne, Jeffrey Shallit, and Luca Q. Zamboni, A Taxonomy of Morphic Sequences, arXiv preprint arXiv:1711.10807 [cs.FL], Nov 29 2017.
J.-P. Allouche and M. Mendes France, Automata and Automatic Sequences, in: Axel F. and Gratias D. (eds), Beyond Quasicrystals. Centre de Physique des Houches, vol 3. Springer, Berlin, Heidelberg, pp. 293-367, 1995; DOI https://doi.org/10.1007/978-3-662-03130-8_11.
J.-P. Allouche and M. Mendes France, Automata and Automatic Sequences, in: Axel F. and Gratias D. (eds), Beyond Quasicrystals. Centre de Physique des Houches, vol 3. Springer, Berlin, Heidelberg, pp. 293-367, 1995; DOI https://doi.org/10.1007/978-3-662-03130-8_11. [Local copy]
P. Arnoux and E. Harriss, What is a Rauzy Fractal?, Notices Amer. Math. Soc., 61 (No. 7, 2014), 768-770, also p. 704 and front cover.
Aayush Rajasekaran, Narad Rampersad, and Jeffrey Shallit, Overpals, Underlaps, and Underpals, In: Brlek S., Dolce F., Reutenauer C., Vandomme É. (eds) Combinatorics on Words, WORDS 2017, Lecture Notes in Computer Science, vol 10432.
|
|
|
FORMULA
|
a(n) = floor((n+2)*r) - floor((n+1)*r) where r=phi/(1+2*phi) and phi is the Golden Ratio. - Benoit Cloitre, Nov 10 2003
The first formula by Cloitre is just one of an infinite family of formulas. Using phi^2=1+phi, it follows that r=phi/(1+2*phi)=2-phi. Then from floor(-x)=-floor(x)-1 for non-integer x, it follows that a(n)=2-A014675(n)=2-(floor((n+2)* phi)-floor((n+1)*phi)). - Michel Dekking, Aug 27 2016
|
|
|
EXAMPLE
|
The word is 010010100100101001010010010100...
Over the alphabet {a,b} this is a, b, a, a, b, a, b, a, a, b, a, a, b, a, b, a, a, b, a, b, a, a, b, a, a, b, a, b, a, a, b, a, a, b, a, b, a, a, b, a, b, a, a, b, a, a, b, a, b, a, a, b, a, b, a, a, b, a, a, b, a, b, a, a, b, a, a, b, a, b, a, a, b, a, b, a, a, b, a, a, b, a, b, a, a, b, a, a, b, a, b, a, a, b, a, b, a, a, b, a, a, b, a, b, a, ...
|
|
|
MAPLE
|
z := proc(m) option remember; if m=0 then [0] elif m=1 then [0, 1] else [op(z(m-1)), op(z(m-2))]; fi; end; z(12);
M:=19; S[0]:=`0`; S[1]:=`01`; for n from 2 to M do S[n]:=cat(S[n-1], S[n-2]); od:
t0:=S[M]: l:=length(t0); for i from 1 to l do lprint(i-1, substring(t0, i..i)); od: # N. J. A. Sloane, Nov 01 2006
|
|
|
MATHEMATICA
|
Nest[ Flatten[ # /. {0 -> {0, 1}, 1 -> {0}}] &, {0}, 10] (* Robert G. Wilson v, Mar 05 2005 *)
Table[Floor[(n + 2) #] - Floor[(n + 1) #], {n, 0, 120}] &[2 - GoldenRatio] (* Michael De Vlieger, Aug 15 2016 *)
SubstitutionSystem[{0->{0, 1}, 1->{0}}, {0}, {10}][[1]] (* Harvey P. Dale, Dec 20 2021 *)
|
|
|
PROG
|
(Magma) t1:=[ n le 2 select ["0", "0, 1"][n] else Self(n-1) cat ", " cat Self(n-2) : n in [1..12]]; t1[12];
(Haskell)
a003849 n = a003849_list !! n
a003849_list = tail $ concat fws where
fws = [1] : [0] : (zipWith (++) fws $ tail fws)
(PARI) a(n)=my(k=2); while(fibonacci(k)<=n, k++); while(n>1, while(fibonacci(k--)>n, ); n-=fibonacci(k)); n==1 \\ Charles R Greathouse IV, Feb 03 2014
(PARI) M3849=[2, 2, 1, 0]/*L(k), S(k), L(k-1), S(k-1)*/; A003849(n)={while(n>M3849[1], M3849=vecextract(M3849, [1, 2, 1, 2])+[M3849[3], M3849[4]<<M3849[1], 0, 0]); bittest(M3849[2], n)} \\ Much faster at the expense of using ~ Nmax/5 bytes of memory (~ 250 KB for n <= 1.3e6). - M. F. Hasler, Apr 07 2021
(Python)
def fib(n):
"""Return the concatenation of A003849(0..F-1) where F is the smallest
Fibonacci number > n, so that the result contains a(n) at index n."""
a, b = '10'
while len(b)<=n:
a, b = b, b + a
(Python)
from math import isqrt
def A003849(n): return 2-(n+2+isqrt(m:=5*(n+2)**2)>>1)+(n+1+isqrt(m-10*n-15)>>1) # Chai Wah Wu, Aug 25 2022
|
|
|
CROSSREFS
|
Sequences mentioned in the Allouche et al. "Taxonomy" paper, listed by example number: 1: A003849, 2: A010060, 3: A010056, 4: A020985 and A020987, 5: A191818, 6: A316340 and A273129, 18: A316341, 19: A030302, 20: A063438, 21: A316342, 22: A316343, 23: A003849 minus its first term, 24: A316344, 25: A316345 and A316824, 26: A020985 and A020987, 27: A316825, 28: A159689, 29: A049320, 30: A003849, 31: A316826, 32: A316827, 33: A316828, 34: A316344, 35: A043529, 36: A316829, 37: A010060.
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
|
|
|
KEYWORD
|
nonn,easy,nice
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
| |
|
|
A003622
|
|
The Wythoff compound sequence AA: a(n) = floor(n*phi^2) - 1, where phi = (1+sqrt(5))/2.
(Formerly M3278)
|
|
+10
84
|
|
|
|
1, 4, 6, 9, 12, 14, 17, 19, 22, 25, 27, 30, 33, 35, 38, 40, 43, 46, 48, 51, 53, 56, 59, 61, 64, 67, 69, 72, 74, 77, 80, 82, 85, 88, 90, 93, 95, 98, 101, 103, 106, 108, 111, 114, 116, 119, 122, 124, 127, 129, 132, 135, 137, 140, 142, 145, 148, 150, 153, 156, 158, 161, 163, 166
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,2
|
|
|
COMMENTS
|
Also, integers with "odd" Zeckendorf expansions (end with ...+F_2 = ...+1) (Fibonacci-odd numbers); first column of Wythoff array A035513; from a 3-way splitting of positive integers. [Edited by Peter Munn, Sep 16 2022]
Also, numbers k such that A005206(k) = A005206(k+1). Also k such that A022342(A005206(k)) = k+1 (for all other k's this is k). - Michele Dondi (bik.mido(AT)tiscalenet.it), Dec 30 2001
Also, positions of 1's in A139764, the smallest term in Zeckendorf representation of n. - John W. Layman, Aug 25 2011
Numbers with an odd number of trailing 1's in their dual Zeckendorf representation (A104326), i.e., numbers k such that A356749(k) is odd.
The asymptotic density of this sequence is 1 - 1/phi (A132338). (End)
|
|
|
REFERENCES
|
A. Brousseau, Fibonacci and Related Number Theoretic Tables. Fibonacci Association, San Jose, CA, 1972, p. 62.
R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 1990, p. 307-308 of 2nd edition.
C. Kimberling, "Stolarsky interspersions", Ars Combinatoria 39 (1995) 129-138.
D. R. Morrison, "A Stolarsky array of Wythoff pairs", in A Collection of Manuscripts Related to the Fibonacci Sequence. Fibonacci Assoc., Santa Clara, CA, 1980, pp. 134-136.
J. Roberts, Lure of the Integers, Math. Assoc. America, 1992, p. 10.
N. J. A. Sloane and Simon Plouffe, Encyclopedia of Integer Sequences, Academic Press, 1995: this sequence appears twice, as both M3277 and M3278.
|
|
|
LINKS
|
Aviezri S. Fraenkel, The Raleigh game, INTEGERS: Electronic Journal of Combinatorial Number Theory 7.2 (2007): A13, 10 pages. See Table 1.
|
|
|
FORMULA
|
a(n) = floor(n*phi) + n - 1. [Corrected by Jianing Song, Aug 18 2022]
a(n) = floor(floor(n*phi)*phi) = A000201(A000201(n)). [See the Mathematics Stack Exchange link for a proof of the equivalence of the definition. - Jianing Song, Aug 18 2022]
G.f.: 1 - (1-x)*Sum_{n>=1} x^a(n) = 1/1 + x/1 + x^2/1 + x^3/1 + x^5/1 + x^8/1 + ... + x^F(n)/1 + ... (continued fraction where F(n)=n-th Fibonacci number). - Paul D. Hanna, Aug 16 2002
|
|
|
MAPLE
|
n+floor(n*(1+sqrt(5))/2)-1 ;
# Maple code for the Wythoff compound sequences, from N. J. A. Sloane, Mar 30 2016
# The Wythoff compound sequences: Let A = A000201, B = A001950. Then AA = A003622, AB = A003623, BA = A035336, BB = A101864. The eight triples AAA, AAB, ..., BBB are A134859, A134860, A035337, A134862, A134861, A134863, A035338, A134864, resp.
# Assume files out1, out2 contain lists of the terms in the base sequences A and B from their b-files
read out1; read out2; b[0]:=b1: b[1]:=b2:
w2:=(i, j, n)->b[i][b[j][n]];
w3:=(i, j, k, n)->b[i][b[j][b[k][n]]];
for i from 0 to 1 do
lprint("name=", i);
lprint([seq(b[i][n], n=1..100)]):
od:
for i from 0 to 1 do for j from 0 to 1 do
lprint("name=", i, j);
lprint([seq(w2(i, j, n), n=1..100)]);
od: od:
for i from 0 to 1 do for j from 0 to 1 do for k from 0 to 1 do
lprint("name=", i, j, k);
lprint([seq(w3(i, j, k, n), n=1..100)]);
od: od: od:
|
|
|
MATHEMATICA
|
With[{c=GoldenRatio^2}, Table[Floor[n c]-1, {n, 70}]] (* Harvey P. Dale, Jun 11 2011 *)
|
|
|
PROG
|
(PARI) a(n)=floor(n*(sqrt(5)+3)/2)-1
(PARI) a(n) = (sqrtint(n^2*5)+n*3)\2 - 1; \\ Michel Marcus, Sep 17 2022
(Haskell)
a003622 n = a003622_list !! (n-1)
a003622_list = filter ((elem 1) . a035516_row) [1..]
(Python)
from sympy import floor
from mpmath import phi
(Python)
from math import isqrt
|
|
|
CROSSREFS
|
The Wythoff compound sequences: Let A = A000201, B = A001950. Then AA = A003622, AB = A003623, BA = A035336, BB = A101864. The eight triples AAA, AAB, ..., BBB are A134859, A134860, A035337, A134862, A134861, A134863, A035338, A134864, resp.
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
|
|
|
KEYWORD
|
nonn,easy,nice
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
| |
|
|
A005614
|
|
The binary complement of the infinite Fibonacci word A003849. Start with 1, apply 0->1, 1->10, iterate, take limit.
|
|
+10
83
|
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,1
|
|
|
COMMENTS
|
Previous name was: The infinite Fibonacci word (start with 1, apply 0->1, 1->10, iterate, take limit).
With offset 1 this is the characteristic sequence for Wythoff A-numbers A000201=[1,3,4,6,...].
Eric Angelini's comment made me think that if 1 is defined to be the number of 0's between successive 1's in a string of 0's and 1's, then this string is 101. Applying the same operation to the digits of 101 leads to 101101, the iteration leads to successive palindromes of lengths given by A001911, up to a(n). - Rémi Schulz, Jul 06 2010
The limiting mean of the first n terms is phi - 1; the limiting variance is phi (A001622). - Clark Kimberling, Mar 12 2014
Apply the difference operator to every column of the Wythoff difference array, A080164, to get an array of Fibonacci numbers, F(h). Replace each F(h) with h, and apply the difference operator to every column. In the resulting array, every column is A005614. - Clark Kimberling, Mar 02 2015
|
|
|
REFERENCES
|
J.-P. Allouche and J. Shallit, Automatic Sequences, Cambridge Univ. Press, 2003.
G. Melançon, Factorizing infinite words using Maple, MapleTech journal, vol. 4, no. 1, 1997, pp. 34-42, esp. p. 36.
|
|
|
LINKS
|
Glen Joyce C. Dulatre, Jamilah V. Alarcon, Vhenedict M. Florida, and Daisy Ann A. Disu, On Fractal Sequences, DMMMSU-CAS Science Monitor (2016-2017) Vol. 15 No. 2, 109-113.
|
|
|
FORMULA
|
Define strings S(0)=1, S(1)=10, thereafter S(n)=S(n-1)S(n-2); iterate. Sequence is S(oo). The individual S(n)'s are given in A036299.
a(n) = floor((n+2)*u) - floor((n+1)*u), where u = (-1 + sqrt(5))/2.
If we read the present sequence as the digits of a decimal constant c = 0.101101011011010 ... then we have the series representation c = Sum_{n >= 1} 1/10^floor(n*phi). An alternative representation is c = Sum_{n >= 1} 1/10^floor(n/phi) - 10/9.
The constant 9*c has the simple continued fraction representation [0; 1, 10, 10, 100, 1000, ..., 10^Fibonacci(n), ...]. See A010100.
Using this result we can find the alternating series representation c = 1/9 - 9*Sum_{n >= 1} (-1)^(n+1)*(1 + 10^Fibonacci(3*n+1))/( (10^(Fibonacci(3*n - 1)) - 1)*(10^(Fibonacci(3*n + 2)) - 1) ). The series converges very rapidly: for example, the first 10 terms of the series give a value for c accurate to more than 5.7 million decimal places. Cf. A014565. (End)
|
|
|
EXAMPLE
|
The infinite word is 101101011011010110101101101011...
|
|
|
MAPLE
|
Digits := 50; u := evalf((1-sqrt(5))/2); A005614 := n->floor((n+1)*u)-floor(n*u);
|
|
|
MATHEMATICA
|
Nest[ Flatten[ # /. {0 -> {1}, 1 -> {1, 0}}] &, {1}, 10] (* Robert G. Wilson v, Jan 30 2005 *)
|
|
|
PROG
|
(PARI) a(n, w1, s0, s1)=local(w2); for(i=2, n, w2=[ ]; for(k=1, length(w1), w2=concat(w2, if(w1[ k ], s1, s0))); w1=w2); w2
for(n=2, 10, print(n" "a(n, [ 0 ], [ 1 ], [ 1, 0 ]))) \\ Gives successive convergents to sequence
(PARI) /* for m>=1 compute exactly A183136(m+1)+1 terms of the sequence */
r=(1+sqrt(5))/2; v=[1, 0]; for(n=2, m, v=concat(v, vector(floor((n+1)/r), i, v[i])); a(n)=v[n]; ) /* Benoit Cloitre, Jan 16 2013 */
(Haskell)
a005614 n = a005614_list !! n
a005614_list = map (1 -) a003849_list
(Magma) [Floor((n+1)*(-1+Sqrt(5))/2)-Floor(n*(-1+Sqrt(5))/2): n in [1..100]]; // Vincenzo Librandi, Jan 17 2019
(Python)
from math import isqrt
def A005614(n): return (n+isqrt(m:=5*(n+2)**2)>>1)-(n+1+isqrt(m-10*n-15)>>1) # Chai Wah Wu, Aug 17 2022
|
|
|
CROSSREFS
|
Binary complement of A003849, which is the standard form of this sequence.
Cf. A000045 (Fibonacci numbers), A001468, A001911, A005206 (partial sums), A014565, A014675, A022342, A036299, A044432, A221150, A221151, A221152.
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
|
|
|
KEYWORD
|
nonn,easy,nice
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
| |
|
|
A005206
|
|
Hofstadter G-sequence: a(0) = 0; a(n) = n - a(a(n-1)) for n > 0.
(Formerly M0436)
|
|
+10
82
|
|
|
|
0, 1, 1, 2, 3, 3, 4, 4, 5, 6, 6, 7, 8, 8, 9, 9, 10, 11, 11, 12, 12, 13, 14, 14, 15, 16, 16, 17, 17, 18, 19, 19, 20, 21, 21, 22, 22, 23, 24, 24, 25, 25, 26, 27, 27, 28, 29, 29, 30, 30, 31, 32, 32, 33, 33, 34, 35, 35, 36, 37, 37, 38, 38, 39, 40, 40, 41, 42, 42, 43, 43, 44, 45, 45, 46, 46, 47
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,4
|
|
|
COMMENTS
|
Rule for finding n-th term: a(n) = An, where An denotes the Fibonacci antecedent to (or right shift of) n, which is found by replacing each F(i) in the Zeckendorf expansion (obtained by repeatedly subtracting the largest Fibonacci number you can until nothing remains) by F(i-1) (A1=1). For example: 58 = 55 + 3, so a(58) = 34 + 2 = 36. - Diego Torres (torresvillarroel(AT)hotmail.com), Nov 24 2002
From Albert Neumueller (albert.neu(AT)gmail.com), Sep 28 2006: (Start)
A recursively built tree structure can be obtained from the sequence (see Hofstadter, p. 137):
14 15 16 17 18 19 20 21
\ / / \ / \ / /
9 10 11 12 13
\ / / \ /
6 7 8
\ / /
\ / /
\ / /
4 5
\ /
\ /
\ /
\ /
\ /
3
/
2
\ /
1
To construct the tree: node n is connected with the node a(n) below
n
/
a(n)
For example, since a(7) = 4:
7
/
4
If the nodes of the tree are read from bottom to top, left to right, one obtains the positive integers: 1, 2, 3, 4, 5, 6, ... The tree has a recursive structure, since the construct
/
x
\ /
x
can be repeatedly added on top of its own ends, to construct the tree from its root: e.g.,
/
x
/ \ /
x x
\ / /
x x
\ /
\ /
x
When moving from a node to a lower connected node, one is moving to the parent. Parent node of n: floor((n+1)/tau). Left child of n: floor(tau*n). Right child of n: floor(tau*(n+1))-1 where tau=(1+sqrt(5))/2. (See the Sillke link.)
(End)
Properties coming from the 1st problem proposed during the 45th Czech and Slovak Mathematical Olympiad in 1996 (see IMO Compendium link):
-> a(n) >= a(n-1) for any positive integer n,
-> a(n) - a(n-1) belongs to {0,1},
-> No integer n exists such that a(n-1) = a(n) = a(n+1). (End)
For n >= 1, find n in the Wythoff array (A035513). a(n) is the number that precedes n in its row, using the preceding column of the extended Wythoff array (A287870) if n is at the start of the (unextended) row. - Peter Munn, Sep 17 2022
See my 2023 publication on Hofstadter's G-sequence for a proof of the equality of (a(n)) with the sequence A073869. - Michel Dekking, Apr 28 2024
|
|
|
REFERENCES
|
D. R. Hofstadter, Goedel, Escher, Bach: an Eternal Golden Braid, Random House, 1980, p. 137.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
|
|
|
LINKS
|
L. Carlitz, Fibonacci Representations, Fibonacci Quarterly, volume 6, number 4, October 1968, pages 193-220. a(n) = e(n) at equation 1.10 or 2.11 and see equation 3.8 recurrence.
D. R. Hofstadter, Eta-Lore [Cached copy, with permission]
The IMO Compendium, Problem 1, 45th Czech and Slovak Mathematical Olympiad 1996.
|
|
|
FORMULA
|
a(n) = floor((n+1)*tau) - n - 1 = A000201(n+1)-n-1, where tau = (1+sqrt(5))/2; or a(n) = floor(sigma*(n+1)) where sigma = (sqrt(5)-1)/2.
a(0)=0, a(1)=1, a(n) = n - a(floor(n/tau)). - Benoit Cloitre, Nov 27 2002
a(0) = 0, a(n+1) = a(n) + d(n) and d(0) = 1, d(n+1)=1-d(n)*d(a(n)). - Pierre Letouzey, Sep 09 2015
A generalization of Diego Torres's 2002 comment as a formula: if n = Sum_{i in S} A000045(i+1), where S is a set of positive integers, then a(n) = Sum_{i in S} A000045(i). - Peter Munn, Sep 28 2022
|
|
|
MAPLE
|
H:=proc(n) option remember; if n=0 then 0 elif n=1 then 1 else n-H(H(n-1)); fi; end proc: seq(H(n), n=0..76);
|
|
|
MATHEMATICA
|
a[0] = 0; a[n_] := a[n] = n - a[a[n - 1]]; Array[a, 77, 0]
(* Second program: *)
Fold[Append[#1, #2 - #1[[#1[[#2]] + 1 ]] ] &, {0}, Range@ 76] (* Michael De Vlieger, Nov 13 2017 *)
|
|
|
PROG
|
(Haskell)
a005206 n = a005206_list !! n
a005206_list = 0 : zipWith (-) [1..] (map a005206 a005206_list)
(Haskell)
a005206 = sum . zipWith (*) a000045_list . a213676_row . a000201 . (+ 1)
(PARI) first(n)=my(v=vector(n)); v[1]=1; for(k=2, n, v[k]=k-v[v[k-1]]); concat(0, v) \\ Charles R Greathouse IV, Sep 02 2015
(Magma) [Floor((n+1)*(1+Sqrt(5))/2)-n-1: n in [0..80]]; // Vincenzo Librandi, Nov 19 2016
(Python)
from math import isqrt
|
|
|
CROSSREFS
|
a(n):=Sum{k=1..n} h(k), n >= 1, with h(k):= A005614(k-1) and a(0):=0.
|
|
|
KEYWORD
|
nonn,easy,nice
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
| |
|
|
A003842
|
|
The infinite Fibonacci word: start with 1, repeatedly apply the morphism 1->12, 2->1, take limit; or, start with S(0)=2, S(1)=1, and for n>1 define S(n)=S(n-1)S(n-2), then the sequence is S(oo).
|
|
+10
52
|
|
|
|
1, 2, 1, 1, 2, 1, 2, 1, 1, 2, 1, 1, 2, 1, 2, 1, 1, 2, 1, 2, 1, 1, 2, 1, 1, 2, 1, 2, 1, 1, 2, 1, 1, 2, 1, 2, 1, 1, 2, 1, 2, 1, 1, 2, 1, 1, 2, 1, 2, 1, 1, 2, 1, 2, 1, 1, 2, 1, 1, 2, 1, 2, 1, 1, 2, 1, 1, 2, 1, 2, 1, 1, 2, 1, 2, 1, 1, 2, 1, 1, 2, 1, 2, 1, 1, 2, 1, 1, 2, 1, 2, 1, 1, 2, 1, 2, 1, 1, 2, 1, 1, 2, 1, 2, 1
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,2
|
|
|
COMMENTS
|
Or, fixed point of the morphism 1->12, 2->1, starting from a(1) = 2.
A Sturmian word, as are all versions of this sequence. This means that if one slides a window of length n along the sequence, one sees exactly n+1 different subwords (see A213975). For a proof, see for example Chap. 2 of Lothaire (2002).
The limiting mean of the first n terms is 3 - phi, where phi is the golden ratio (A001622); the limiting variance is 2 - phi. - Clark Kimberling, Mar 12 2014
The Wikipedia article on L-system Example 1 is "Algae" given by the axiom: A and rules: A -> AB, B -> A. The sequence G(n) = G(n-1)G(n-2) yields this sequence when A -> 1, B -> 2. - Michael Somos, Jan 12 2015
|
|
|
REFERENCES
|
J.-P. Allouche and J. Shallit, Automatic Sequences, Cambridge Univ. Press, 2003.
Jean Berstel, "Fibonacci words—a survey." In The book of L, pp. 13-27. Springer Berlin Heidelberg, 1986.
J. Berstel and J. Karhumaki, Combinatorics on words - a tutorial, Bull. EATCS, #79 (2003), pp. 178-228.
E. Bombieri and J. Taylor, Which distribution of matter diffracts? An initial investigation, in International Workshop on Aperiodic Crystals (Les Houches, 1986), J. de Physique, Colloq. C3, 47 (1986), C3-19 to C3-28.
Aldo de Luca and Stefano Varricchio, Finiteness and regularity in semigroups and formal languages. Monographs in Theoretical Computer Science. An EATCS Series. Springer-Verlag, Berlin, 1999. x+240 pp. ISBN: 3-540-63771-0 MR1696498 (2000g:68001). See p. 25.
J. C. Lagarias, Number Theory and Dynamical Systems, pp. 35-72 of S. A. Burr, ed., The Unreasonable Effectiveness of Number Theory, Proc. Sympos. Appl. Math., 46 (1992). Amer. Math. Soc. - see p. 64.
G. Melançon, Factorizing infinite words using Maple, MapleTech journal, vol. 4, no. 1, 1997, pp. 34-42, esp. p. 36.
|
|
|
LINKS
|
J.-P. Allouche and M. Mendes France, Automata and Automatic Sequences, in: Axel F. and Gratias D. (eds), Beyond Quasicrystals. Centre de Physique des Houches, vol 3. Springer, Berlin, Heidelberg, pp. 293-367, 1995; DOI https://doi.org/10.1007/978-3-662-03130-8_11.
J.-P. Allouche and M. Mendes France, Automata and Automatic Sequences, in: Axel F. and Gratias D. (eds), Beyond Quasicrystals. Centre de Physique des Houches, vol 3. Springer, Berlin, Heidelberg, pp. 293-367, 1995; DOI https://doi.org/10.1007/978-3-662-03130-8_11. [Local copy]
|
|
|
FORMULA
|
Define strings S(0)=2, S(1)=1, S(n)=S(n-1)S(n-2); iterate. Sequence is S(infinity).
|
|
|
EXAMPLE
|
Over the alphabet {a,b} this is the sequence a, b, a, a, b, a, b, a, a, b, a, a, b, a, b, a, a, b, a, b, a, a, b, a, a, b, a, b, a, a, b, a, a, b, a, b, a, a, b, a, b, a, a, b, a, a, b, a, b, a, a, b, a, b, a, a, b, a, a, b, a, b, a, a, b, a, a, b, a, b, a, a, b, a, b, a, a, b, a, a, b, a, b, a, a, b, a, a, b, a, b, a, a, b, a, b, a, a, b, a, a, b, a, b, a, ...
|
|
|
MATHEMATICA
|
Nest[ Flatten[ # /. {1 -> {1, 2}, 2 -> {1}}] &, {1}, 10] (* Robert G. Wilson v, Mar 04 2005 *)
Table[n + 1 - Floor[((1 + Sqrt[5])/2)*Floor[2*(n + 1)/(1 + Sqrt[5])]], {n, 1, 50}] (* G. C. Greubel, May 18 2017 *)
SubstitutionSystem[{1->{1, 2}, 2->{1}}, {1}, {10}][[1]] (* Harvey P. Dale, Nov 19 2022 *)
|
|
|
PROG
|
(Haskell)
a003842 n = a003842_list !! n
a003842_list = tail $ concat fws where
fws = [2] : [1] : (zipWith (++) fws $ tail fws)
(PARI) for(n=1, 50, print1(n+1 - floor(((1+sqrt(5))/2)*floor(2*(n+1)/(1+sqrt(5)))), ", ")) \\ G. C. Greubel, May 18 2017
a = [1]
while len(a)<length: a = [j for i in a for j in [[], [1, 2], [1]][i]]
(Python)
def aupto(nn):
S, Fnm2, Fnm1 = [1, 2], 1, 2
while len(S) < nn+1:
S += S[:min(Fnm2, nn+1-len(S))]
Fnm2, Fnm1 = Fnm1, Fnm1+Fnm2
return S
(Python)
from math import isqrt
def A003842(n): return n+2-((m:=(n+2+isqrt(5*(n+2)**2)>>1)-n-2)+isqrt(5*m**2)>>1) # Chai Wah Wu, Aug 26 2022
|
|
|
CROSSREFS
|
A003849 is another common version of this sequence.
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
|
|
|
KEYWORD
|
nonn,nice,easy
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
Search completed in 0.037 seconds
|
