login
A375802
Lexicographically earliest sequence of positive integers such that the sum of the inverses of the indices where the sequence has the same value is at most 1.
1
1, 2, 2, 3, 3, 2, 3, 3, 3, 3, 4, 4, 4, 4, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6
OFFSET
1,2
COMMENTS
In other words, if a(n_1) = ... = a(n_k) with n_1 < ... < n_k then 1/n_1 + ... + 1/n_k <= 1.
Each positive integer appears in the sequence, a finite number of times. This is a consequence of the fact that the greedy algorithm for Egyptian fractions terminates in a finite number of steps for any rational starting value.
FORMULA
a(A157248(n)) <= a(A157248(n+1)).
EXAMPLE
The first terms, alongside the sums of the inverses of the indices so far where the sequence has the same value, are:
n a(n) Sums
-- ---- ---------
1 1 1
2 2 1/2
3 2 5/6
4 3 1/4
5 3 9/20
6 2 1
7 3 83/140
8 3 201/280
9 3 2089/2520
10 3 2341/2520
PROG
(PARI) { b = vector(6); for (n = 1, 87, for (v = 1, oo, if (b[v] + 1/n <= 1, b[v] += 1/n; print1 (v", "); break; ); ); ); }
(Python)
from fractions import Fraction
from itertools import count, islice
from collections import defaultdict
def agen(): # generator of terms
invsum, mink = defaultdict(int), 1
for n in count(1):
an = next(k for k in count(mink) if invsum[k] + Fraction(1, n) <= 1)
yield an
invsum[an] += Fraction(1, n)
while invsum[mink] == 1: mink += 1
print(list(islice(agen(), 87))) # Michael S. Branicky, Aug 31 2024
CROSSREFS
Sequence in context: A334475 A110012 A233542 * A245908 A023514 A179751
KEYWORD
nonn,easy
AUTHOR
Rémy Sigrist, Aug 29 2024
STATUS
approved