# [seqfan] Re: nth divisor of a number

David Wilson davidwwilson at comcast.net
Sat Mar 31 19:07:26 CEST 2012

```At the risk of an overlong post, I am submitting a table of values of
p(n, d), the limit probability that the nth divisor of an integer is d.
My results agree with Benoit Jubin's table as far as it went. This is
information to create OEIS tabular sequences for numerators and
denominators.

My program was written in C++, it ran quickly, but the problem size was
limited by 64-bit arithmetic. Perhaps my methods would be suitable for
translation into a Mma or some other package. If anyone is interested, I
would be willing to explain my methods (or perhaps it's not worth the
effort).

At any rate, regarding the original question about the most likely nth
divisor of an integer, we have

a(1) = 1 (probability 1)
a(2) = 2 (probability 1/2)
a(3) = 3 or 4 (probability 1/6)
a(4) = 4 (probability 1/12)
a(5) = 6 (probability 1/12)
a(6) = 8 (probability 13/420) [This is almost certainly correct. 8 is
the winner out of divisors <= 20, absolute confirmation would require
checking all divisors <= 32 = [420/13], empirical evidence suggests
larger numbers are unlikely to have large enough probability to unseat 8.]

p(1,2) = 0
p(2,2) = 1/2

p(1,3) = 0
p(2,3) = 1/6
p(3,3) = 1/6

p(1,4) = 0
p(2,4) = 0
p(3,4) = 1/6
p(4,4) = 1/12

p(1,5) = 0
p(2,5) = 1/15
p(3,5) = 1/15
p(4,5) = 1/20
p(5,5) = 1/60

p(1,6) = 0
p(2,6) = 0
p(3,6) = 0
p(4,6) = 1/15
p(5,6) = 1/12
p(6,6) = 1/60

p(1,7) = 0
p(2,7) = 4/105
p(3,7) = 1/21
p(4,7) = 1/35
p(5,7) = 1/70
p(6,7) = 1/84
p(7,7) = 1/420

p(1,8) = 0
p(2,8) = 0
p(3,8) = 0
p(4,8) = 2/35
p(5,8) = 1/42
p(6,8) = 13/420
p(7,8) = 1/84
p(8,8) = 1/840

p(1,9) = 0
p(2,9) = 0
p(3,9) = 4/105
p(4,9) = 1/63
p(5,9) = 13/630
p(6,9) = 11/630
p(7,9) = 1/70
p(8,9) = 11/2520
p(9,9) = 1/2520

p(1,10) = 0
p(2,10) = 0
p(3,10) = 0
p(4,10) = 1/35
p(5,10) = 2/105
p(6,10) = 11/420
p(7,10) = 17/1260
p(8,10) = 11/1260
p(9,10) = 1/280
p(10,10) = 1/2520

p(1,11) = 0
p(2,11) = 8/385
p(3,11) = 2/77
p(4,11) = 7/495
p(5,11) = 16/1155
p(6,11) = 47/6930
p(7,11) = 1/180
p(8,11) = 1/396
p(9,11) = 13/13860
p(10,11) = 1/3080
p(11,11) = 1/27720

p(1,12) = 0
p(2,12) = 0
p(3,12) = 0
p(4,12) = 0
p(5,12) = 0
p(6,12) = 4/231
p(7,12) = 106/3465
p(8,12) = 2/99
p(9,12) = 4/385
p(10,12) = 19/4620
p(11,12) = 19/27720
p(12,12) = 1/27720

p(1,13) = 0
p(2,13) = 16/1001
p(3,13) = 108/5005
p(4,13) = 116/9009
p(5,13) = 529/45045
p(6,13) = 223/45045
p(7,13) = 34/9009
p(8,13) = 571/180180
p(9,13) = 43/25740
p(10,13) = 29/36036
p(11,13) = 19/60060
p(12,13) = 19/360360
p(13,13) = 1/360360

p(1,14) = 0
p(2,14) = 0
p(3,14) = 0
p(4,14) = 16/1001
p(5,14) = 164/15015
p(6,14) = 284/15015
p(7,14) = 356/45045
p(8,14) = 1/143
p(9,14) = 19/3276
p(10,14) = 523/180180
p(11,14) = 23/16380
p(12,14) = 8/15015
p(13,14) = 5/72072
p(14,14) = 1/360360

p(1,15) = 0
p(2,15) = 0
p(3,15) = 0
p(4,15) = 16/1001
p(5,15) = 68/5005
p(6,15) = 2/585
p(7,15) = 25/3003
p(8,15) = 493/90090
p(9,15) = 92/15015
p(10,15) = 691/90090
p(11,15) = 59/15015
p(12,15) = 139/90090
p(13,15) = 97/180180
p(14,15) = 5/72072
p(15,15) = 1/360360

p(1,16) = 0
p(2,16) = 0
p(3,16) = 0
p(4,16) = 0
p(5,16) = 24/1001
p(6,16) = 2/455
p(7,16) = 51/5005
p(8,16) = 59/6006
p(9,16) = 131/20020
p(10,16) = 139/60060
p(11,16) = 1063/360360
p(12,16) = 3/2002
p(13,16) = 97/180180
p(14,16) = 17/72072
p(15,16) = 1/30030
p(16,16) = 1/720720

p(1,17) = 0
p(2,17) = 192/17017
p(3,17) = 1376/85085
p(4,17) = 2164/255255
p(5,17) = 6184/765765
p(6,17) = 93/17017
p(7,17) = 23/7735
p(8,17) = 2069/765765
p(9,17) = 4871/3063060
p(10,17) = 277/278460
p(11,17) = 3317/6126120
p(12,17) = 2039/6126120
p(13,17) = 151/1021020
p(14,17) = 101/2042040
p(15,17) = 7/437580
p(16,17) = 5/2450448
p(17,17) = 1/12252240

p(1,18) = 0
p(2,18) = 0
p(3,18) = 0
p(4,18) = 0
p(5,18) = 0
p(6,18) = 256/17017
p(7,18) = 944/255255
p(8,18) = 2636/255255
p(9,18) = 7654/765765
p(10,18) = 416/58905
p(11,18) = 1154/255255
p(12,18) = 89/36465
p(13,18) = 2609/1531530
p(14,18) = 127/255255
p(15,18) = 41/185640
p(16,18) = 37/875160
p(17,18) = 1/314160
p(18,18) = 1/12252240

p(1,19) = 0
p(2,19) = 3072/323323
p(3,19) = 22976/1616615
p(4,19) = 5536/692835
p(5,19) = 105436/14549535
p(6,19) = 61624/14549535
p(7,19) = 173/51051
p(8,19) = 29/13923
p(9,19) = 2423/1616615
p(10,19) = 20869/19399380
p(11,19) = 3397/5290740
p(12,19) = 107/255816
p(13,19) = 2339/12932920
p(14,19) = 6571/58198140
p(15,19) = 1783/58198140
p(16,19) = 58/4849845
p(17,19) = 1/447678
p(18,19) = 1/5969040
p(19,19) = 1/232792560

p(1,20) = 0
p(2,20) = 0
p(3,20) = 0
p(4,20) = 0
p(5,20) = 0
p(6,20) = 3456/323323
p(7,20) = 13848/1616615
p(8,20) = 14702/1616615
p(9,20) = 747/230945
p(10,20) = 2537/510510
p(11,20) = 12281/3879876
p(12,20) = 15663/3233230
p(13,20) = 32427/12932920
p(14,20) = 230999/116396280
p(15,20) = 5341/8314020
p(16,20) = 4751/19399380
p(17,20) = 607/11639628
p(18,20) = 47/8953560
p(19,20) = 1/4084080
p(20,20) = 1/232792560

On 3/31/2012 1:58 AM, Benoît Jubin wrote:
> And these probabilities are obviously rational numbers, so two OEIS
> tables will be enough!
>
> In addition to the three identities you wrote, we have
> p(n,n) = 1/(lcm{1,...,n}) = 1/A003418(n)
> and
> p(n,d) = 0 if n<  tau(d) = A000005(d)
> and
> p(tau(d),d) = 1/d * product( (q-1)/q , q prime and there is an a with
> q^a<d and q^a does not divide d )
> and in particular, if r is prime, then
> p(2,r) = 1/r * product( ( (q-1)/q , q prime, q<r ).
>
> Forgetting p(1,1) = 1, the table begins:
>   1/2,
>   1/6,  1/6,
>     0,  1/6, 1/12,
> 1/15, 1/15, 1/20, 1/60,
>     0,    0, 1/15, 1/12, 1/60,
> 4/105, ...
>
> Benoît
>

```