login
This site is supported by donations 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)
120

%I M0257 N0091

%S 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,

%T 10,11,11,11,11,11,12,12,12,12,12,12,13,13,13,13,13,13,14,14,14,14,14,

%U 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

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

%C It is understood that a(n) is taken to be the smallest number >= a(n-1) which is compatible with the description.

%C In other words, this is the lexicographically earliest non-decreasing sequence of positive numbers which is equal to its RUNS transform. - _N. J. A. Sloane_, Nov 07 2018

%C Also called Silverman's sequence.

%C Vardi gives several identities satisfied by A001463 and this sequence.

%C 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_, Nov 06 2005

%C 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]

%C 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

%D G. Everest, A. van der Poorten, I. Shparlinski and T. Ward, Recurrence Sequences, Amer. Math. Soc., 2003; p. 10.

%D R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 1990, p. 66.

%D R. K. Guy, Unsolved Problems in Number Theory, E25.

%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

%D 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.

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

%H T. D. Noe, <a href="/A001462/b001462.txt">Table of n, a(n) for n = 1..10000</a>

%H Altug Alkan, <a href="https://doi.org//10.1155/2018/8517125">On a Generalization of Hofstadter's Q-Sequence: A Family of Chaotic Generational Structures</a>, Complexity (2018) Article ID 8517125.

%H B. Cloitre, N. J. A. Sloane and M. J. Vandermast, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL6/Cloitre/cloitre2.html">Numerical analogues of Aronson's sequence</a>, J. Integer Seqs., Vol. 6 (2003), #03.2.2.

%H B. Cloitre, N. J. A. Sloane and M. J. Vandermast, <a href="https://arxiv.org/abs/math/0305308">Numerical analogues of Aronson's sequence</a>, arXiv:math/0305308 [math.NT], 2003.

%H M. Gardner, <a href="/A005130/a005130_1.pdf">Letter to N. J. A. Sloane</a>, Jun 20 1991.

%H S. W. Golomb, <a href="http://www.jstor.org/stable/2314829">Problem 5407</a>, Amer. Math. Monthly, 73 (1966), 674.

%H J. Grytczuk, <a href="http://dx.doi.org/10.1016/j.disc.2003.10.022">Another variation on Conway's recursive sequence</a>, Discr. Math. 282 (2004), 149-161.

%H Brady Haran and Tony Padilla, <a href="http://www.youtube.com/watch?v=VDD6FDhKCYA">Six Sequences</a>, Numberphile video (2013).

%H D. Marcus and N. J. Fine, <a href="http://www.jstor.org/stable/2314296">Solutions to Problem 5407</a>, Amer. Math. Monthly 74 (1967), 740-743.

%H Christian Perfect, <a href="http://aperiodical.com/2013/07/integer-sequence-reviews-on-numberphile-or-vice-versa/">Integer sequence reviews on Numberphile (or vice versa)</a>, 2013.

%H Y.-F. S. Petermann, <a href="http://dx.doi.org/10.1006/jnth.1995.1076">On Golomb's self-describing sequence</a>, J. Number Theory 53 (1995), 13-24.

%H Y.-F. S. Petermann, <a href="http://dx.doi.org/10.1007/BF01270611">On Golomb's self-describing sequence, II</a>, Arch. Math. (Basel) 67 (1996), 473-477.

%H Y.-F. S. Petermann, <a href="http://dx.doi.org/10.1524/anly.1998.18.3.245">Is the error term wild enough?</a>, Analysis (Munich) 18 (1998), 245-256.

%H Y.-F. S. Petermann, and Jean-Luc Remy, <a href="http://projecteuclid.org/euclid.ijm/1256044933">Golomb's self-described sequence and functional-differential equations</a>, Illinois J. Math. 42 (1998), 420-440.

%H Y.-F. S. Petermann, J.-L. Remy and I. Vardi, <a href="https://doi.org/10.1006/aama.2001.0750">Discrete derivatives of sequences</a>, Adv. in Appl. Math. 27 (2001), 562-84.

%H J. L. Rémy, <a href="http://dx.doi.org/10.1006/jnth.1997.2154">Sur la suite autodécrite de Golomb</a>, J. Number Theory, 66 (1997), 1-28.

%H J. Sauerberg and L. Shu, <a href="http://www.jstor.org/stable/2974579">The long and the short on counting sequences</a>, Amer. Math. Monthly, 104 (1997), 306-317.

%H N. J. A. Sloane, <a href="http://neilsloane.com/doc/sg.txt">My favorite integer sequences</a>, in Sequences and their Applications (Proceedings of SETA '98).

%H N. J. A. Sloane, <a href="http://neilsloane.com/doc/g4g7.pdf">Seven Staggering Sequences</a>.

%H N. J. A. Sloane, <a href="/A001149/a001149.pdf">Handwritten notes on Self-Generating Sequences, 1970</a> (note that A1148 has now become A005282)

%H N. J. A. Sloane, <a href="/transforms.txt">Transforms</a>

%H N. J. A. Sloane, Coordination Sequences, Planing Numbers, and Other Recent Sequences (II), Experimental Mathematics Seminar, Rutgers University, Jan 31 2019, <a href="https://vimeo.com/314786942">Part I</a>, <a href="https://vimeo.com/314790822">Part 2</a>, <a href="https://oeis.org/A320487/a320487.pdf">Slides.</a> (Mentions this sequence)

%H I. Vardi, <a href="http://dx.doi.org/10.1016/0022-314X(92)90024-J">The error term in Golomb's sequence</a>, J. Number Theory, 40 (1992), 1-11. (See also the Math. Review, 93d:11103)

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/SilvermansSequence.html">Silverman's Sequence</a>

%H <a href="/index/Cor#core">Index entries for "core" sequences</a>

%H <a href="/index/Aa#aan">Index entries for sequences of the a(a(n)) = 2n family</a>

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

%F a(1) = 1; a(n+1) = 1 + a(n+1-a(a(n))). - _Colin Mallows_

%F 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

%F G.f.: Sum_{n>0} a(n) x^n = Sum_{k>0} x^a(k). - _Michael Somos_, Oct 21 2006

%e 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.

%e 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

%p N:= 10000: A001462[1]:= 1: B[1]:= 1: A001462[2]:= 2:

%p for n from 2 while B[n-1] <= N do

%p B[n]:= B[n-1] + A001462[n];

%p for j from B[n-1]+1 to B[n] do A001462[j]:= n end do

%p end do:

%p seq(A001462[j],j=1..N); # _Robert Israel_, Oct 30 2012

%t 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 *)

%t GolSeq[n_]:=Nest[(k = 0; Flatten[# /. m_Integer :> (ConstantArray[++k,m])]) &, {1, 2}, n]

%t 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 *)

%o (PARI) a = [1, 2, 2]; for(n=3, 20, for(i=1, a[n], a = concat(a, n))); a /* _Michael Somos_, Jul 16 1999 */

%o (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 */

%o (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

%o (Haskell)

%o a001462 n = a001462_list !! (n-1)

%o a001462_list = 1 : 2 : 2 : g 3 where

%o g x = (replicate (a001462 x) x) ++ g (x + 1)

%o -- _Reinhard Zumkeller_, Feb 09 2012

%o (Python)

%o a=[0, 1, 2, 2]

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

%o print a[1:] # _Indranil Ghosh_, Jul 05 2017

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

%Y Golomb-type sequences over various substrates (from _Glen Whitney_, Oct 12 2015):

%Y A000002 and references therein (over periodic sequences),

%Y A109167 (over nonnegative integers),

%Y A080605 (over odd numbers),

%Y A080606 (over even numbers),

%Y A080607 (over multiples of 3),

%Y A169682 (over primes),

%Y A013189 (over squares),

%Y A013322 (over triangular numbers),

%Y A250983 (over integral sums of itself).

%K easy,nonn,nice,core

%O 1,2

%A _N. J. A. Sloane_

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified April 23 09:35 EDT 2019. Contains 322385 sequences. (Running on oeis4.)