cp's OEIS Frontend

A307720 Lexicographically earliest sequence of positive integers in which, for all positive k, there are exactly k pairs of consecutive terms whose product is k.

%I A307720 #100 Nov 18 2023 11:44:41
%S A307720 1,1,2,1,3,1,3,2,2,2,2,2,3,2,3,2,3,3,3,3,3,3,3,3,3,3,4,2,4,2,4,2,4,2,
%T A307720 4,3,4,3,4,3,4,3,4,3,4,3,5,1,5,1,5,1,7,1,7,1,7,1,7,2,5,2,5,2,5,2,5,2,
%U A307720 5,2,7,2,7,2,7,2,7,2,7,2,7,2,7,3,5,3,5,3,5,3,5,3,5,3,5,3,5,3,6,3,6,3,6,3,6,3,6,3,6,3,6,3,6,3,6,3,7,3,7,3,7,3,7,3,7,3,7,3,7,3,7,3,7,3,7,3,8,2,8
%N A307720 Lexicographically earliest sequence of positive integers in which, for all positive k, there are exactly k pairs of consecutive terms whose product is k.
%C A307720 All natural integers will appear sooner or later in the sequence (from the definition) - but mostly "later"! Indeed, the sequence increases very slowly: after 100000 terms the smallest term not yet present is 32.
%C A307720 Here is, in the same range, a sample of the count {term, occurrences} so far:
%C A307720 {1,192},{2,396},{3,618},{4,796},{5,1160},{6,1296},{7,2294},{8,2080},{9,2489},{10,2826},{11,3487},{12,1596},{13,2295},{14,1960},{15,2370},{16,2640},{17,4097},{18,2214},{19,4598},{20,2770},{21,3759},{22,4477},{23,5612},{24,4884},{25,5825},{26,6006},{27,6359},{28,4676},{29,5481},{30,3060},{31,1411},{32,0},{33,182},{34,0},{35,315},{36,0},{37,1221},{38,0},{39,214},{40,0},{41,1353},{42,0},{43,1183},{44,0},{45,0},{46,0},{47,1058},{48,0},{49,172},{50,0},{51,0},{52,0},{53,580},...
%C A307720 After 100000 terms, the first products that are not yet present are (the primes): 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, ... and (the composites) 118, 122, 134, ...
%C A307720 Here is again a sample so far (100000 terms computed) of {product, number of occurrences of the product}:
%C A307720 {1,1},{2,2},{3,3},{4,4},{5,5},{6,6},{7,7},{8,8},{9,9},{10,10},{11,11},{12,12},{13,13},{14,14},{15,15},{16,16},{17,17},{18,18},{19,19},{20,20},{21,21},{22,22},{23,23},{24,24},{25,25},{26,26},{27,27},{28,28},{29,29},{30,30},{31,31},{32,32},{33,33},{34,34},{35,35},{36,36},{37,37},{38,38},{39,39},{40,40},{41,41},{42,42},{43,43},{44,44},{45,45},{46,46},{47,47},{48,48},{49,49},{50,50},{51,51},{52,52},{53,53},{54,54},{55,55},{56,56},{57,57},{58,58},{59,0},{60,60},{61,0},{62,62},{63,63},{64,64},{65,65},{66,66},{67,0},{68,68},{69,69},{70,70},{71,0},{72,72},{73,0},{74,74},{75,75},{76,76},{77,77},{78,78},{79,0},{80,80},{81,81},{82,82},{83,0},{84,84},{85,85},{86,86},{87,87},{88,88},{89,0},{90,90},{91,91},{92,92},{93,93},{94,94},{95,95},{96,96},{97,0},{98,98},{99,99},{100,100},{101,0},{102,102},{103,0},{104,104},{105,105},{106,106},{107,0},{108,108},{109,0},{110,110},{111,111},{112,112},{113,0},{114,114},{115,115},{116,116},{117,117},{118,0},{119,119},{120,120},{121,121},{122,0},{123,123},{124,124},{125,125},{126,126},{127,0},{128,128},{129,129},{130,130},{131,0},{132,132},{133,133},{134,0},{135,135},{136,136},{137,0},{138,138},{139,0},{140,140},{141,141},{142,0},...
%C A307720 Comment from _N. J. A. Sloane_, Oct 19 2021: (Start)
%C A307720 Theorem. This sequence can also be defined by a greedy algorithm. That is, let b(1)=1, and for n >= 1, let b(n+1) be the smallest positive integer k such that m = k*b(n) has appeared at most n-1 times in the list [b(i)*b(i+1): i=1..n-1]. Then b(n) = a(n) for all n >= 1.
%C A307720 (Note that for n=1 the list is empty, and so we take k = b(1) = 1.)
%C A307720 Remark: The theorem is not obvious and requires a proof, given in a link below. "Lexicographically earliest" sequences often require some backtracking, but the point of the theorem is that no backtracking is needed here.
%C A307720 The proof also shows that there are infinitely many 1's in the sequence, and that each k appears k times in the sequence of products a(i)*a(i+1). (End)
%H A307720 Jean-Marc Falcoz, <a href="/A307720/b307720.txt">Table of n, a(n) for n = 1..28446</a>
%H A307720 William Cheswick, <a href="/A348248/a348248_2.png">Colored plot of first 200 terms of A307720</a> (See Comments in A348248 for explanation of colors in these pictures)
%H A307720 William Cheswick, <a href="/A348248/a348248_3.png">Colored plot of first 1000 terms of A307720</a>
%H A307720 William Cheswick, <a href="/A348248/a348248_4.png">Colored plot of first 10000 terms of A307720</a>
%H A307720 William Cheswick, <a href="/A348248/a348248.png">Colored plot of first 10^5 terms of A307720</a>
%H A307720 William Cheswick, <a href="/A348248/a348248_1.png">Colored plot of first 10^6 terms of A307720</a>
%H A307720 Robert Dougherty-Bliss, <a href="/A307720/a307720_1.png">Graph of first 10^6 terms with successive points joined.</a> [This effectively fills the region between the trajectories of the left and right hands with black ink.]
%H A307720 Rémy Sigrist, <a href="/A307720/a307720.png">Scatterplot of the first 10000000 terms</a>
%H A307720 Rémy Sigrist, <a href="/A307720/a307720.gp.txt">PARI program for A307720</a>
%H A307720 N. J. A. Sloane, <a href="/A307720/a307720.txt">Table of n, a(n) for n = 1..1000000</a> [Computed using Rémy Sigrist's PARI program]
%H A307720 N. J. A. Sloane, <a href="/A307720/a307720_3.txt">Proof of theorem that every number appears</a>
%H A307720 N. J. A. Sloane, <a href="https://arxiv.org/abs/2301.03149">"A Handbook of Integer Sequences" Fifty Years Later</a>, arXiv:2301.03149 [math.NT], 2023, p. 9.
%H A307720 Chai Wah Wu, <a href="/A348446/a348446_2.png">Scatterplot of the first 100 million terms of A348446</a> [shows how the lead changes between the left and right hands]
%e A307720 The sequence starts with 1,1,2,1,3,1,3,2,2,2,2,2,3,...
%e A307720 The product a(n)*a(n+1) = 1 is true exactly once [this is the product a(1) * a(2) = 1 * 1 = 1];
%e A307720 The product a(n)*a(n+1) = 2 is true exactly twice [these are the products a(2) * a(3) = 1 * 2 = 2 and a(3) * a(4) = 2 * 1 = 2];
%e A307720 The product a(n)*a(n+1) = 3 is true exactly three times [these are the products a(4) * a(5) = 1 * 3 = 3 ; a(5) * a(6) = 3 * 1 = 3, and a(6) * a(7) = 1 * 3 = 3];
%e A307720 ...
%e A307720 The product a(n)*a(n+1) = 4 is true exactly four times [these are the products a(8) * a(9) = 2 * 2 = 4 ; a(9) * a(10) = 2 * 2 = 4 ; a(10) * a(11) = 2 * 2 = 4 ; a(11) * a(12) = 2 * 2 = 4] ; and so on.
%t A307720 nmax = 1000; time = {0}; v = 1;
%t A307720 A307720 = Reap[For[n = 1, n <= nmax, n++, Sow[v]; For[o = 1, True, o++, While[Length[time] < o*v, time = Join[time, Table[0, {Length[time]}]]]; If[time[[o*v]]+1 <= o*v, time[[o*v]]++; v = o; Break[]]]]][[2, 1]] (* _Jean-François Alcover_, Oct 23 2021, after _Rémy Sigrist_'s PARI program *)
%o A307720 (PARI) \\ See Links section.
%o A307720 (Python)
%o A307720 from itertools import islice
%o A307720 from collections import Counter
%o A307720 def A307720(): # generator of terms. Greedy algorithm
%o A307720     yield 1
%o A307720     c, b = Counter(), 1
%o A307720     while True:
%o A307720         k, kb = 1, b
%o A307720         while c[kb] >= kb:
%o A307720             k += 1
%o A307720             kb += b
%o A307720         c[kb] += 1
%o A307720         b = k
%o A307720         yield k
%o A307720 A307720_list = list(islice(A307720(),100)) # _Chai Wah Wu_, Oct 21 2021
%Y A307720 Cf. A307707 (same idea, but with the sum of contiguous terms instead of the product), A307730 (the products), A307630 (when n appears), A307631 (indices of records), A307632 (indices of primes), A348241 and A348242 (bisections), A307633 and A307634 (RUNS transforms of bisections), A348446 (bisection differences), A348458 (partial sums).
%Y A307720 See also A307747.
%K A307720 nonn,look,nice
%O A307720 1,3
%A A307720 _Eric Angelini_ and _Jean-Marc Falcoz_, Apr 24 2019
%E A307720 Definition revised slightly by _Allan C. Wechsler_, Apr 24 2019
%E A307720 Example clarified by _Rémy Sigrist_, Oct 24 2021