|
| |
|
|
A001462
|
|
Golomb's sequence: a(n) is the number of times n occurs, starting with a(1) = 1.
(Formerly M0257 N0091)
|
|
55
|
|
|
|
1, 2, 2, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 6, 7, 7, 7, 7, 8, 8, 8, 8, 9, 9, 9, 9, 9, 10, 10, 10, 10, 10, 11, 11, 11, 11, 11, 12, 12, 12, 12, 12, 12, 13, 13, 13, 13, 13, 13, 14, 14, 14, 14, 14, 14, 15, 15, 15, 15, 15, 15, 16, 16, 16, 16, 16, 16, 16, 17, 17, 17, 17, 17, 17, 17, 18, 18, 18, 18, 18, 18, 18, 19
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,2
|
|
|
COMMENTS
|
It is understood that a(n) is taken to be the smallest number >= a(n-1) which is compatible with the description.
Also called Silverman's sequence.
Vardi gives several identities satisfied by A001463 and this sequence.
We can interpret A001462 as a triangle: start with 1; 2,2; 3,3; and proceed by letting the row sum of row m-1 be the number of elements of row m. The partial sums of the row sums give 1, 5, 11, 38, 272, ... Conjecture: this proceeds as Lionel Levile's sequence A014644. See also A113676. - Floor van Lamoen, fvlamoen(AT)hotmail.com, Nov 06 2005.
The g.f. -z*(-1+z**4+z**7-z**8+z**9-z**3-z-z**11+z**12)/(1+z)/(z**2+1)/(z-1)**2 conjectured by Simon Plouffe in his 1992 dissertation is wrong. - N. J. A. Sloane, May 13 2008
a(A095114(n)) = n and a(m) < m for m < A095114(n). [Reinhard Zumkeller, Feb 09 2012]
|
|
|
REFERENCES
|
G. Everest, A. van der Poorten, I. Shparlinski and T. Ward, Recurrence Sequences, Amer. Math. Soc., 2003; p. 10.
S. W. Golomb, Problem 5407, Amer. Math. Monthly, 73 (1966), 674.
R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 1990, p. 66.
J. Grytczuk, Another variation on Conway's recursive sequence, Discr. Math. 282 (2004), 149-161.
R. K. Guy, Unsolved Problems in Number Theory, E25.
D. Marcus and N. J. Fine, Solutions to Problem 5407, Amer. Math. Monthly 74 (1967), 740-743.
Petermann, Y.-F. S., On Golomb's self-describing sequence, J. Number Theory 53 (1995), 13-24.
Petermann, Y.-F. S., On Golomb's self-describing sequence, II, Arch. Math. (Basel) 67 (1996), 473-477.
Petermann, Y.-F. S., Is the error term wild enough? Analysis (Munich) 18 (1998), 245-256.
Petermann, Y.-F. S. and Remy, Jean-Luc, Golomb's self-described sequence and functional-differential equations, Illinois J. Math. 42 (1998), 420-440.
J. L. Remy, J. Number Theory, 66 (1997), 1-28.
J. Sauerberg and L. Shu, The long and the short on counting sequences, Amer. Math. Monthly, 104 (1997), 306-317.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane, Seven Staggering Sequences, in Homage to a Pied Puzzler, E. Pegg Jr., A. H. Schoen and T. Rodgers (editors), A. K. Peters, Wellesley, MA, 2009, pp. 93-110.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
I. Vardi, The error term in Golomb's sequence, J. Number Theory, 40 (1992), 1-11. (See also the Math. Review, 93d:11103)
|
|
|
LINKS
|
T. D. Noe, Table of n, a(n) for n = 1..10000
B. Cloitre, N. J. A. Sloane and M. J. Vandermast, Numerical analogues of Aronson's sequence, J. Integer Seqs., Vol. 6 (2003), #03.2.2.
B. Cloitre, N. J. A. Sloane and M. J. Vandermast, Numerical analogues of Aronson's sequence (math.NT/0305308)
Y.-F. S. Petermann, J.-L. Remy and I. Vardi, Discrete derivatives of sequences, Adv. in Appl. Math. 27 (2001), 562-84.
_Simon Plouffe_, Approximations de S\'{e}ries G\'{e}n\'{e}ratrices et Quelques Conjectures, Dissertation, Universit\'{e} du Qu\'{e}bec \`{a} Montr\'{e}al, 1992.
_Simon Plouffe_, 1031 Generating Functions and Conjectures, Universit\'{e} du Qu\'{e}bec \`{a} Montr\'{e}al, 1992.
N. J. A. Sloane, My favorite integer sequences, in Sequences and their Applications (Proceedings of SETA '98).
N. J. A. Sloane, Seven Staggering Sequences.
Eric Weisstein's World of Mathematics, Silverman's Sequence
Index entries for "core" sequences
Index entries for sequences of the a(a(n)) = 2n family
|
|
|
FORMULA
|
a(n) = phi^(2-phi)*n^(phi-1) + E(n), where phi is the golden number (1+sqrt(5))/2 (Marcus and Fine) and E(n) is an error term which Vardi shows is O( n^(phi-1) / log n ).
a(1) = 1; a(n+1) = 1 + a(n+1-a(a(n))). - Colin Mallows
a(1)=1, a(2)=2 and for a(1)+a(2)+..+a(n-1) < k <= a(1)+a(2)+...+a(n) we have a(k)=n - Benoit Cloitre, Oct 07 2003
G.f.: Sum_{k>0} x^a(k). - Michael Somos, Oct 21 2006
|
|
|
EXAMPLE
|
a(1) = 1, so 1 only appears once. The next term is therefore 2, which means 2 appears twice and so a(3) is also 2 but a(4) must be 3. And so on.
|
|
|
MAPLE
|
N:= 10000: A001462[1]:= 1: B[1]:= 1: A001462[2]:= 2:
for n from 2 while B[n-1] <= N do
B[n]:= B[n-1] + A001462[n];
for j from B[n-1]+1 to B[n] do A001462[j]:= n end do
end do:
seq(A001462[j], j=1..N);
|
|
|
MATHEMATICA
|
a[1] = 1; a[n_] := a[n] = 1 + a[n - a[a[n - 1]]]; Table[ a[n], {n, 84}] (from Robert G. Wilson v, Aug 26 2005)
|
|
|
PROG
|
(PARI) a=[ 1, 2, 2 ]; for(n=3, 20, for(i=1, a[ n ], a=concat(a, n))); a
(PARI) A001462(n)={ local(A, t, i); if(n<3, max(0, n), A=vector(n); t=A[i=2]=2; for(k=3, n, A[k]=A[k-1]+if(t--==0, t=A[i++ ]; 1)); A[n])} /* Michael Somos Oct 21 2006 */
(MAGMA) [ n eq 1 select 1 else 1+Self(n-Self(Self(n-1))) : n in [1..100] ]; - from Sergei Haller (sergei(AT)sergei-haller.de), Dec 21 2006
(Haskell)
a001462 n = a001462_list !! (n-1)
a001462_list = 1 : 2 : 2 : g 3 where
g x = (replicate (a001462 x) x) ++ g (x + 1)
-- Reinhard Zumkeller, Feb 09 2012
|
|
|
CROSSREFS
|
Cf. A000002, A001463 (partial sums).
Sequence in context: A126848 A067085 A055086 * A082462 A005041 A030530
Adjacent sequences: A001459 A001460 A001461 * A001463 A001464 A001465
|
|
|
KEYWORD
|
easy,nonn,nice,core
|
|
|
AUTHOR
|
N. J. A. Sloane.
|
|
|
EXTENSIONS
|
Improved Maple program by Robert Israel, Oct 30 2012
|
|
|
STATUS
|
approved
|
| |
|
|
