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

Author

Jwalin Bhatt, May 14 2025

Keywords

• nonn

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.

Examples

			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    |
		

Links

• Jwalin Bhatt, Table of n, a(n) for n = 1..10000
• Wikipedia, Yule-Simon distribution

Crossrefs

Cf. A245254, A383855.

Programs

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]