login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A001462 Golomb's sequence: a(n) is the number of times n occurs, starting with a(1) = 1.
(Formerly M0257 N0091)
145
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.

In other words, this is the lexicographically earliest nondecreasing sequence of positive numbers which is equal to its RUNS transform. - N. J. A. Sloane, Nov 07 2018

Also called Silverman's sequence.

Vardi gives several identities satisfied by A001463 and this sequence.

We can interpret this sequence 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, Nov 06 2005

A Golomb-type 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 cross-references for more examples. - Ivan Neretin, Mar 29 2015

From Amiram Eldar, Jun 19 2021: (Start)

Named after the American mathematician Solomon Wolf Golomb (1932-2016).

Guy (2004) called it "Golomb's self-histogramming sequence", while in previous editions of his book (1981 and 1994) he called it "Silverman's sequence" after David Silverman. (End)

REFERENCES

Graham Everest, Alf van der Poorten, Igor Shparlinski and Thomas Ward, Recurrence Sequences, Amer. Math. Soc., 2003; p. 10.

Ronald L. Graham, Donald E. Knuth and Oren Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 1990, p. 66.

Richard K. Guy, Unsolved Problems in Number Theory, 3rd Edition, Springer, 2004, Section E25, p. 347-348.

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).

LINKS

T. D. Noe, Table of n, a(n) for n = 1..10000

Altug Alkan, On a Generalization of Hofstadter's Q-Sequence: A Family of Chaotic Generational Structures, Complexity (2018), Article ID 8517125.

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.

Benoit Cloitre, N. J. A. Sloane and Matthew J. Vandermast, Numerical analogues of Aronson's sequence, arXiv:math/0305308 [math.NT], 2003.

Martin Gardner, Letter to N. J. A. Sloane, Jun 20 1991.

Solomon W. Golomb, Problem 5407, Amer. Math. Monthly, Vol. 73, No. 6 (1966), p. 674.

Jarosław Grytczuk, Another variation on Conway's recursive sequence, Discr. Math., Vol. 282, No. 1-3 (2004), pp. 149-161.

Brady Haran and Tony Padilla, Six Sequences, Numberphile video (2013).

Brady Haran and N. J. A. Sloane, Planing Sequences (Le Rabot), Numberphile video, June 2021.

Daniel Marcus and N. J. Fine, Solutions to Problem 5407, Amer. Math. Monthly, Vol. 74, No. 6 (1967), pp. 740-743.

Christian Perfect, Integer sequence reviews on Numberphile (or vice versa), 2013.

Y.-F. S. Petermann, On Golomb's self-describing sequence, J. Number Theory, Vol. 53, No. 1 (1995), pp. 13-24.

Y.-F. S. Petermann, On Golomb's self-describing sequence, II, Arch. Math. (Basel) 67 (1996), 473-477.

Y.-F. S. Petermann, Is the error term wild enough?, Analysis (Munich), Vol. 18 (1998), pp. 245-256.

Y.-F. S. Pétermann and Jean-Luc Rémy, Golomb's self-described sequence and functional-differential equations, Illinois J. Math., Vol. 42, No. 3 (1998), pp. 420-440.

Y.-F. S. Pétermann, Jean-Luc Rémy and Ilan Vardi, Discrete derivatives of sequences, Adv. in Appl. Math., Vol. 27 (2001), pp. 562-84.

Jean-Luc Rémy, Sur la suite autodécrite de Golomb, J. Number Theory, Vo. 66, No. 1 (1997), pp. 1-28.

Jim Sauerberg and Linghsueh Shu, The long and the short on counting sequences, Amer. Math. Monthly, Vol. 104, No. 4 (1997), pp. 306-317.

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 Self-Generating Sequences, 1970. (note that A1148 has now become A005282)

N. J. A. Sloane, Transforms.

N. J. A. Sloane, Coordination Sequences, Planing Numbers, and Other Recent Sequences (II), Experimental Mathematics Seminar, Rutgers University, Jan 31 2019, Part I, Part 2, Slides. (Mentions this sequence)

Ilan Vardi, The error term in Golomb's sequence, J. Number Theory, Vol. 40 (1992), pp. 1-11. (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^(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_{n>0} a(n) x^n = Sum_{k>0} x^a(k). - Michael Somos, Oct 21 2006

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]

Conjecture: a(n) >= n^(phi-1) for all n. - Jianing Song, Aug 19 2021

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.

G.f. = x + 2*x^2 + 2*x^3 + 3*x^4 + 3*x^5 + 4*x^6 + 4*x^7 + 4*x^8 + ... - Michael Somos, Nov 07 2018

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); # 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[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] ]; // 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

(Python)

a=[0, 1, 2, 2]

for n in range(3, 21):a+=[n for i in range(1, a[n] + 1)]

a[1:] # Indranil Ghosh, Jul 05 2017

CROSSREFS

Cf. A001463 (partial sums) and A262986 (start of first run of length n).

Golomb-type 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).

Applying "ee Rabot" to this sequence gives A319434.

Sequence in context: A067085 A321578 A055086 * A357021 A082462 A276581

Adjacent sequences:  A001459 A001460 A001461 * A001463 A001464 A001465

KEYWORD

easy,nonn,nice,core

AUTHOR

N. J. A. Sloane

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 6 12:35 EDT 2022. Contains 357264 sequences. (Running on oeis4.)