[seqfan] Re: nth divisor of a number

[David Wilson]

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
>