cp's OEIS Frontend

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.

%I A375802 #15 Aug 31 2024 08:32:24
%S A375802 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,
%T A375802 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,
%U A375802 5,5,5,5,5,5,5,5,5,5,5,5,5,5,6,6,6,6,6
%N 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.
%C A375802 In other words, if a(n_1) = ... = a(n_k) with n_1 < ... < n_k then 1/n_1 + ... + 1/n_k <= 1.
%C A375802 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.
%H A375802 Rémy Sigrist, <a href="/A375802/b375802.txt">Table of n, a(n) for n = 1..10000</a>
%H A375802 Wikipedia, <a href="https://en.wikipedia.org/wiki/Greedy_algorithm_for_Egyptian_fractions">Greedy algorithm for Egyptian fractions</a>
%H A375802 <a href="/index/Ed#Egypt">Index entries for sequences related to Egyptian fractons</a>
%F A375802 a(A157248(n)) <= a(A157248(n+1)).
%e A375802 The first terms, alongside the sums of the inverses of the indices so far where the sequence has the same value, are:
%e A375802   n   a(n)  Sums
%e A375802   --  ----  ---------
%e A375802    1     1  1
%e A375802    2     2  1/2
%e A375802    3     2  5/6
%e A375802    4     3  1/4
%e A375802    5     3  9/20
%e A375802    6     2  1
%e A375802    7     3  83/140
%e A375802    8     3  201/280
%e A375802    9     3  2089/2520
%e A375802   10     3  2341/2520
%o A375802 (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;););); }
%o A375802 (Python)
%o A375802 from fractions import Fraction
%o A375802 from itertools import count, islice
%o A375802 from collections import defaultdict
%o A375802 def agen(): # generator of terms
%o A375802     invsum, mink = defaultdict(int), 1
%o A375802     for n in count(1):
%o A375802         an = next(k for k in count(mink) if invsum[k] + Fraction(1, n) <= 1)
%o A375802         yield an
%o A375802         invsum[an] += Fraction(1, n)
%o A375802         while invsum[mink] == 1: mink += 1
%o A375802 print(list(islice(agen(), 87))) # _Michael S. Branicky_, Aug 31 2024
%Y A375802 Cf. A157248, A323725.
%K A375802 nonn,easy
%O A375802 1,2
%A A375802 _Rémy Sigrist_, Aug 29 2024