cp's OEIS Frontend

A316774 a(n) = n for n < 2, a(n) = freq(a(n-1),n) + freq(a(n-2),n) for n >= 2, where freq(i,j) is the number of times i appears in [a(0),a(1),...,a(j-1)].

%I A316774 #61 Oct 13 2022 11:08:01
%S A316774 0,1,2,2,4,3,2,4,5,3,3,6,4,4,8,5,3,6,6,6,8,6,7,6,7,8,5,6,10,8,5,8,9,6,
%T A316774 9,10,4,7,8,9,9,8,11,8,9,13,6,10,12,4,7,10,8,13,11,4,9,13,9,10,12,7,7,
%U A316774 12,9,11,11,8,14,11,6,15,11,7,13,11,11,16,9,10
%N A316774 a(n) = n for n < 2, a(n) = freq(a(n-1),n) + freq(a(n-2),n) for n >= 2, where freq(i,j) is the number of times i appears in [a(0),a(1),...,a(j-1)].
%C A316774 In other words, a(n) = (number of times a(n-1) has appeared) plus (number of times a(n-2) has appeared). - _N. J. A. Sloane_, Dec 13 2019
%C A316774 What is the asymptotic behavior of this sequence?
%C A316774 Does it contain every positive integer at least once?
%C A316774 Does it contain every positive integer at most finitely many times?
%C A316774 Additional comments from Peter Illig's "Puzzles" link below (Start):
%C A316774 Sometimes referred to as "The Devil's Sequence" (by me), due to the early presence of three consecutive 6's (and my inability to understand it). The next time a number occurs three times in a row isn't until a(355677).
%C A316774 If each n does appear only finitely many times, approximately how many times does it appear? (It seems to be close to 2n.)
%C A316774 What are the best possible upper/lower bounds on a(n)?
%C A316774 Let r(k) be the smallest n such that {0,1,2,...,k} is contained in {a(0),...,a(n)}. What is the asymptotic behavior of r(k)? (It seems to be close to k^2/2.)
%C A316774 (End)
%H A316774 Alois P. Heinz, <a href="/A316774/b316774.txt">Table of n, a(n) for n = 0..65536</a>
%H A316774 "Horseshoe_Crab" Reddit User, <a href="http://www.reddit.com/r/mathriddles/comments/318rzm/properties_of_a_strange_rather_meta_sequence_not/?st=jjixq1qm&amp;sh=ef4e12e0">Properties of a Strange, Rather Meta Sequence</a>. [In case this link breaks, the main point of the discussion is to propose the sequence and suggest other initial values. - _N. J. A. Sloane_, Dec 13 2019]
%H A316774 Peter Illig, <a href="https://peterillig.xyz/problems.html">Problems</a>. [No date, probably 2018]
%H A316774 Samuel B. Reid, <a href="/A316774/a316774_1.png">Density plot of one billion terms</a>
%H A316774 Rémy Sigrist, <a href="/A316774/a316774.png">Density plot of the first 10000000 terms</a>
%e A316774 For n=4, a(n-1) = a(n-2) = 2, and 2 appears twice in the first 4 terms. So a(4) = 2 + 2 = 4.
%p A316774 b:= proc() 0 end:
%p A316774 a:= proc(n) option remember; local t;
%p A316774       t:= `if`(n<2, n, b(a(n-1))+b(a(n-2)));
%p A316774       b(t):= b(t)+1; t
%p A316774     end:
%p A316774 seq(a(n), n=0..200);  # _Alois P. Heinz_, Jul 12 2018
%t A316774 a = prev = {0, 1};
%t A316774 Do[
%t A316774 AppendTo[prev, Count[a, prev[[1]]] + Count[a, prev[[2]]]];
%t A316774 AppendTo[a, prev[[3]]];
%t A316774 prev = prev[[2 ;;]] , {78}]
%t A316774 a (* _Peter Illig_, Jul 12 2018 *)
%o A316774 (Python)
%o A316774 from itertools import islice
%o A316774 from collections import Counter
%o A316774 def agen():
%o A316774     a = [0, 1]; c = Counter(a); yield from a
%o A316774     while True:
%o A316774         a = [a[-1], c[a[-1]] + c[a[-2]]]; c[a[-1]] += 1; yield a[-1]
%o A316774 print(list(islice(agen(), 80))) # _Michael S. Branicky_, Oct 13 2022
%Y A316774 Cf. A001462, A316973 (freq(n)), A316905 (when n appears), A316984 (when n last appears), A330439 (total number of times a(n) has appeared so far).
%Y A316774 For records see A330330, A330331.
%Y A316774 See A306246 and A329934 for similar sequences with different initial conditions.
%Y A316774 A330332 considers the frequencies of the three previous terms.
%K A316774 nonn,look
%O A316774 0,3
%A A316774 _Peter Illig_, Jul 12 2018
%E A316774 Definition clarified by _N. J. A. Sloane_, Dec 13 2019