

A001462


Golomb's sequence: a(n) is the number of times n occurs, starting with a(1) = 1.
(Formerly M0257 N0091)


65



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(n1) 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 m1 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, Nov 06 2005
a(A095114(n)) = n and a(m) < n for m < A095114(n).  Reinhard Zumkeller, Feb 09 2012 [First inequality corrected from a(m) < m by Glen Whitney, Oct 06 2015]
A Golombtype sequence, that is, one with the property of being a sequence of run length of itself, can be built over any sequence with distinct terms by repeating each term a corresponding number of times, in the same manner as a(n) is built over natural numbers. See crossreferences for more examples.  Ivan Neretin, Mar 29 2015


REFERENCES

G. Everest, A. van der Poorten, I. Shparlinski and T. Ward, Recurrence Sequences, Amer. Math. Soc., 2003; p. 10.
R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. AddisonWesley, Reading, MA, 1990, p. 66.
R. K. Guy, Unsolved Problems in Number Theory, E25.
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. 93110.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).


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, arXiv:math/0305308 [math.NT], 2003.
M. Gardner, Letter to N. J. A. Sloane, Jun 20 1991.
S. W. Golomb, Problem 5407, Amer. Math. Monthly, 73 (1966), 674.
J. Grytczuk, Another variation on Conway's recursive sequence, Discr. Math. 282 (2004), 149161.
Brady Haran and Tony Padilla, Six Sequences, Numberphile video (2013).
D. Marcus and N. J. Fine, Solutions to Problem 5407, Amer. Math. Monthly 74 (1967), 740743.
Christian Perfect, Integer sequence reviews on Numberphile (or vice versa), 2013.
Y.F. S. Petermann, On Golomb's selfdescribing sequence, J. Number Theory 53 (1995), 1324.
Y.F. S. Petermann, On Golomb's selfdescribing sequence, II, Arch. Math. (Basel) 67 (1996), 473477.
Y.F. S. Petermann, Is the error term wild enough?, Analysis (Munich) 18 (1998), 245256.
Y.F. S. Petermann, and JeanLuc Remy, Golomb's selfdescribed sequence and functionaldifferential equations, Illinois J. Math. 42 (1998), 420440.
Y.F. S. Petermann, J.L. Remy and I. Vardi, Discrete derivatives of sequences, Adv. in Appl. Math. 27 (2001), 56284.
J. L. Remy, Sur la suite autodÃ©crite de Golomb, J. Number Theory, 66 (1997), 128.
J. Sauerberg and L. Shu, The long and the short on counting sequences, Amer. Math. Monthly, 104 (1997), 306317.
N. J. A. Sloane, My favorite integer sequences, in Sequences and their Applications (Proceedings of SETA '98).
N. J. A. Sloane, Seven Staggering Sequences.
N. J. A. Sloane, Handwritten notes on SelfGenerating Sequences, 1970 (note that A1148 has now become A005282)
I. Vardi, The error term in Golomb's sequence, J. Number Theory, 40 (1992), 111. (See also the Math. Review, 93d:11103)
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^(2phi)*n^(phi1) + 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^(phi1) / log n ).
a(1) = 1; a(n+1) = 1 + a(n+1a(a(n))).  Colin Mallows
a(1)=1, a(2)=2 and for a(1) + a(2) + ... + a(n1) < 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[n1] <= N do
B[n]:= B[n1] + A001462[n];
for j from B[n1]+1 to B[n] do A001462[j]:= n end do
end do:
seq(A001462[j], j=1..N); # Robert Israel, Oct 30 2012


MATHEMATICA

a[1] = 1; a[n_] := a[n] = 1 + a[n  a[a[n  1]]]; Table[ a[n], {n, 84}] (* Robert G. Wilson v, Aug 26 2005 *)
GolSeq[n_]:=Nest[(k = 0; Flatten[# /. m_Integer :> (ConstantArray[++k, m])]) &, {1, 2}, n]
GolList=Nest[(k = 0; Flatten[# /.m_Integer :> (ConstantArray[++k, m])]) &, {1, 2}, 7]; AGolList=Accumulate[GolList]; Golomb[n_]:=Which[ n <= Length[GolList], GolList[[n]], n <= Total[GolList], First[FirstPosition[AGolList, _?(# > n &)]], True, $Failed] (* JungHwan Min, Nov 29 2015 *)


PROG

(PARI) a = [1, 2, 2]; for(n=3, 20, for(i=1, a[n], a = concat(a, n))); a /* Michael Somos, Jul 16 1999 */
(PARI) {a(n) = my(A, t, i); if( n<3, max(0, n), A = vector(n); t = A[i=2] = 2; for(k=3, n, A[k] = A[k1] + if( t==0, t = A[i++]; 1)); A[n])}; /* Michael Somos, Oct 21 2006 */
(MAGMA) [ n eq 1 select 1 else 1+Self(nSelf(Self(n1))) : n in [1..100] ]; // Sergei Haller (sergei(AT)sergeihaller.de), Dec 21 2006
(Haskell)
a001462 n = a001462_list !! (n1)
a001462_list = 1 : 2 : 2 : g 3 where
g x = (replicate (a001462 x) x) ++ g (x + 1)
 Reinhard Zumkeller, Feb 09 2012
(Python)
a=[0, 1, 2, 2]
for n in xrange(3, 21):a+=[n for i in xrange(1, a[n] + 1)]
print a[1:] # Indranil Ghosh, Jul 05 2017


CROSSREFS

Cf. A001463 (partial sums) and A262986 (start of first run of length n).
Golombtype sequences over various substrates (from Glen Whitney, Oct 12 2015):
A000002 and references therein (over periodic sequences),
A109167 (over nonnegative integers),
A080605 (over odd numbers),
A080606 (over even numbers),
A080607 (over multiples of 3),
A169682 (over primes),
A013189 (over squares),
A013322 (over triangular numbers),
A250983 (over integral sums of itself).
Sequence in context: A232753 A067085 A055086 * A082462 A276581 A005041
Adjacent sequences: A001459 A001460 A001461 * A001463 A001464 A001465


KEYWORD

easy,nonn,nice,core,changed


AUTHOR

N. J. A. Sloane


STATUS

approved



