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.

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

Offset

1,3

Comments

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.

Here is, in the same range, a sample of the count {term, occurrences} so far:

{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},...

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

Here is again a sample so far (100000 terms computed) of {product, number of occurrences of the product}:

{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},...

Comment from N. J. A. Sloane, Oct 19 2021: (Start)

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.

(Note that for n=1 the list is empty, and so we take k = b(1) = 1.)

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.

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)

Links

Jean-Marc Falcoz, Table of n, a(n) for n = 1..28446

William Cheswick, Colored plot of first 200 terms of A307720 (See Comments in A348248 for explanation of colors in these pictures)

William Cheswick, Colored plot of first 1000 terms of A307720

William Cheswick, Colored plot of first 10000 terms of A307720

William Cheswick, Colored plot of first 10^5 terms of A307720

William Cheswick, Colored plot of first 10^6 terms of A307720

Robert Dougherty-Bliss, Graph of first 10^6 terms with successive points joined. [This effectively fills the region between the trajectories of the left and right hands with black ink.]

Rémy Sigrist, Scatterplot of the first 10000000 terms

Rémy Sigrist, PARI program for A307720

N. J. A. Sloane, Table of n, a(n) for n = 1..1000000 [Computed using Rémy Sigrist's PARI program]

N. J. A. Sloane, Proof of theorem that every number appears

N. J. A. Sloane, "A Handbook of Integer Sequences" Fifty Years Later, arXiv:2301.03149 [math.NT], 2023, p. 9.

Chai Wah Wu, Scatterplot of the first 100 million terms of A348446 [shows how the lead changes between the left and right hands]

Example

The sequence starts with 1,1,2,1,3,1,3,2,2,2,2,2,3,...
The product a(n)*a(n+1) = 1 is true exactly once [this is the product a(1) * a(2) = 1 * 1 = 1];
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];
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];
...
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.

Mathematica

nmax = 1000; time = {0}; v = 1;
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 *)

Prog

(PARI) \\ See Links section.
(Python)
from itertools import islice
from collections import Counter
def A307720(): # generator of terms. Greedy algorithm
    yield 1
    c, b = Counter(), 1
    while True:
        k, kb = 1, b
        while c[kb] >= kb:
            k += 1
            kb += b
        c[kb] += 1
        b = k
        yield k
A307720_list = list(islice(A307720(), 100)) # Chai Wah Wu, Oct 21 2021

Crossrefs

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

See also A307747.

Sequence in context: A249617 A304091 A278801 * A191350 A329616 A304795

Adjacent sequences: A307717 A307718 A307719 * A307721 A307722 A307723

Keyword

nonn,look,nice

Author

Eric Angelini and Jean-Marc Falcoz, Apr 24 2019

Extensions

Definition revised slightly by Allan C. Wechsler, Apr 24 2019

Example clarified by Rémy Sigrist, Oct 24 2021

Status

approved