A383899 A sequence constructed by greedily sampling the Yule-Simon distribution for parameter value 1, to minimize discrepancy selecting the smallest value in case of ties.

1, 2, 1, 3, 1, 4, 1, 2, 1, 5, 1, 6, 1, 2, 1, 3, 1, 7, 1, 2, 1, 8, 1, 9, 1, 2, 1, 4, 1, 3, 1, 2, 1, 10, 1, 11, 1, 2, 1, 3, 1, 5, 1, 2, 1, 4, 1, 12, 1, 2, 1, 3, 1, 13, 1, 2, 1, 6, 1, 14, 1, 2, 1, 3, 1, 4, 1, 2, 1, 5, 1, 15, 1, 2, 1, 7, 1, 3, 1, 2, 1, 16, 1, 17

Offset

1,2

Comments

The geometric mean approaches A245254 in the limit.

The probability mass function of the Yule-Simon distribution with parameter 1 is given by p(k) = 1/(k*(k+1)) for k >= 1.

Links

Jwalin Bhatt, Table of n, a(n) for n = 1..10000

Wikipedia, Yule-Simon distribution

Example

Let p(k) denote the probability of k and c(k) denote the number of occurrences of k among the first n-1 terms; then the expected number of occurrences of k among n random terms is given by n*p(k).
We subtract the actual occurrences c(k) from the expected occurrences and pick the one with the highest value.
| n | n*p(1) - c(1) | n*p(2) - c(2) | n*p(3) - c(3) | choice |
|---|---------------|---------------|---------------|--------|
| 1 |     0.5       |     0.166     |     0.083     |   1    |
| 2 |     0         |     0.333     |     0.166     |   2    |
| 3 |     0.5       |    -0.5       |     0.25      |   1    |
| 4 |     0         |    -0.333     |     0.333     |   3    |
| 5 |     0.5       |    -0.166     |    -0.583     |   1    |

Mathematica

probCountDiff[j_, k_, count_]:=k/(j*(j+1))-Lookup[count, j, 0]
samplePDF[n_]:=Module[{coeffs, unreachedVal, counts, k, probCountDiffs, mostProbable},
  coeffs=ConstantArray[0, n]; unreachedVal=1; counts=<||>;
  Do[probCountDiffs=Table[probCountDiff[i, k, counts], {i, 1, unreachedVal}];
    mostProbable=First@FirstPosition[probCountDiffs, Max[probCountDiffs]];
    If[mostProbable==unreachedVal, unreachedVal++]; coeffs[[k]]=mostProbable;
    counts[mostProbable]=Lookup[counts, mostProbable, 0]+1; , {k, 1, n}]; coeffs]
A383899=samplePDF[120]

Prog

(Python)
from mpmath import iv
def prob_count_diff(j, k, count):
    return  iv.mpf(k)/(j*(j+1)) - count
def sample_yule_simon_distribution(num_coeffs):
    coeffs, unreached_val, counts = [], 1, {}
    for k in range(1, num_coeffs+1):
        prob_count_diffs = [prob_count_diff(i, k, counts.get(i, 0)) for i in range(1, unreached_val+1)]
        most_probable = prob_count_diffs.index(max(prob_count_diffs)) + 1
        unreached_val += most_probable == unreached_val
        coeffs.append(most_probable)
        counts[most_probable] = counts.get(most_probable, 0) + 1
    return coeffs
A383899 = sample_yule_simon_distribution(120)  # Jwalin Bhatt, Dec 16 2025

Crossrefs

Cf. A245254, A383855.

Sequence in context: A289508 A364448 A028920 * A376566 A260738 A055396

Adjacent sequences: A383896 A383897 A383898 * A383900 A383901 A383902

Keyword

nonn

Author

Jwalin Bhatt, May 14 2025

Status

approved