|
%I M0257 N0091 #164 Jan 11 2024 10:59:56
%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 nondecreasing 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 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
%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
%C From _Amiram Eldar_, Jun 19 2021: (Start)
%C Named after the American mathematician Solomon Wolf Golomb (1932-2016).
%C 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)
%D Graham Everest, Alf van der Poorten, Igor Shparlinski and Thomas Ward, Recurrence Sequences, Amer. Math. Soc., 2003; p. 10.
%D Ronald L. Graham, Donald E. Knuth and Oren Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 1990, p. 66.
%D Richard K. Guy, Unsolved Problems in Number Theory, 3rd Edition, Springer, 2004, Section E25, p. 347-348.
%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 Joaquim Bruna, <a href="https://mat.uab.cat/web/matmat/wp-content/uploads/sites/23/2023/11/v2023n04.pdf">The golden ratio from a calculus point of view</a>, Universitat Autònoma de Barcelona, Materials matemàtics (2023) Vol. 2023, No. 4.
%H Benoit Cloitre, N. J. A. Sloane and Matthew J. Vandermast, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL6/Cloitre/cloitre2.html">Numerical analogues of Aronson's sequence</a>, J. Integer Seq., Vol. 6 (2003), Article 03.2.2.
%H Benoit Cloitre, N. J. A. Sloane and Matthew J. Vandermast, <a href="https://arxiv.org/abs/math/0305308">Numerical analogues of Aronson's sequence</a>, arXiv:math/0305308 [math.NT], 2003.
%H Martin Gardner, <a href="/A005130/a005130_1.pdf">Letter to N. J. A. Sloane</a>, Jun 20 1991.
%H Solomon W. Golomb, <a href="http://www.jstor.org/stable/2314829">Problem 5407</a>, Amer. Math. Monthly, Vol. 73, No. 6 (1966), p. 674.
%H Jarosław Grytczuk, <a href="http://dx.doi.org/10.1016/j.disc.2003.10.022">Another variation on Conway's recursive sequence</a>, Discr. Math., Vol. 282, No. 1-3 (2004), pp. 149-161.
%H Brady Haran and Tony Padilla, <a href="http://www.youtube.com/watch?v=VDD6FDhKCYA">Six Sequences</a>, Numberphile video (2013).
%H Brady Haran and N. J. A. Sloane, <a href="https://www.youtube.com/watch?v=R4OvBB9KHMA">Planing Sequences (Le Rabot)</a>, Numberphile video, June 2021.
%H Daniel Marcus and N. J. Fine, <a href="http://www.jstor.org/stable/2314296">Solutions to Problem 5407</a>, Amer. Math. Monthly, Vol. 74, No. 6 (1967), pp. 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, Vol. 53, No. 1 (1995), pp. 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), Vol. 18 (1998), pp. 245-256.
%H Y.-F. S. Pétermann and Jean-Luc Rémy, <a href="http://projecteuclid.org/euclid.ijm/1256044933">Golomb's self-described sequence and functional-differential equations</a>, Illinois J. Math., Vol. 42, No. 3 (1998), pp. 420-440.
%H Y.-F. S. Pétermann, Jean-Luc Rémy and Ilan Vardi, <a href="https://doi.org/10.1006/aama.2001.0750">Discrete derivatives of sequences</a>, Adv. in Appl. Math., Vol. 27 (2001), pp. 562-84.
%H Jean-Luc Rémy, <a href="http://dx.doi.org/10.1006/jnth.1997.2154">Sur la suite autodécrite de Golomb</a>, J. Number Theory, Vo. 66, No. 1 (1997), pp. 1-28.
%H Jim Sauerberg and Linghsueh Shu, <a href="http://www.jstor.org/stable/2974579">The long and the short on counting sequences</a>, Amer. Math. Monthly, Vol. 104, No. 4 (1997), pp. 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 Ilan 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, Vol. 40 (1992), pp. 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
%F 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]
%F Conjecture: a(n) >= n^(phi-1) for all n. - _Jianing Song_, Aug 19 2021
%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 range(3, 21):a+=[n for i in range(1, a[n] + 1)]
%o 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).
%Y Applying "ee Rabot" to this sequence gives A319434.
%K easy,nonn,nice,core
%O 1,2
%A _N. J. A. Sloane_
|
