/
prog.sf
133 lines (123 loc) · 2.74 KB
/
prog.sf
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
#!/usr/bin/ruby
# a(n) = least k such that (k!*e^k)/(sqrt(2*Pi)*k^(k+1/2)) - 1 < 1/2^n.
# https://oeis.org/A247968
# Conjectured formula: a(n) = ceiling(2^n/12) (Charlie Neder, Mar 06 2019).
# Verified up to a(500) using binary search.
# Pseudo-verified up to a(10^4), by checking the formula for k = ceiling(2^n/12) and k = ceiling(2^n/12)-1.
#`( PARI/GP program:
\p 1024
isok(n,k) = (exp(log(1) - log(2)*n) > (exp((lngamma(k+1) + k) - (log(sqrt(2*Pi)) + log(k)*(k + 1/2))) - 1));
a(n) = for(k=1, oo, if(isok(n, k), return(k)));
)
local Num!PREC = 2048
for n in (1..100) {
var t = bsearch_min(1, 2**n, {|k|
exp(log(1) - log(2)*n) <=> (exp((lngamma(k+1) + k) - (log(sqrt(2*Num.pi)) + log(k)*(k + 1/2))) - 1)
})
#~ var t = bsearch_min(1, 2**n, {|k|
#~ (1 / 2**n) <=> ((gamma(k+1) * exp(k)) / (sqrt(2*Num.pi) * k**(k + 1/2)) - 1)
#~ })
assert_eq(t, ceil(2**n / 12))
say "#{n} #{t}"
}
__END__
1 1
2 1
3 1
4 2
5 3
6 6
7 11
8 22
9 43
10 86
11 171
12 342
13 683
14 1366
15 2731
16 5462
17 10923
18 21846
19 43691
20 87382
21 174763
22 349526
23 699051
24 1398102
25 2796203
26 5592406
27 11184811
28 22369622
29 44739243
30 89478486
31 178956971
32 357913942
33 715827883
34 1431655766
35 2863311531
36 5726623062
37 11453246123
38 22906492246
39 45812984491
40 91625968982
41 183251937963
42 366503875926
43 733007751851
44 1466015503702
45 2932031007403
46 5864062014806
47 11728124029611
48 23456248059222
49 46912496118443
50 93824992236886
51 187649984473771
52 375299968947542
53 750599937895083
54 1501199875790166
55 3002399751580331
56 6004799503160662
57 12009599006321323
58 24019198012642646
59 48038396025285291
60 96076792050570582
61 192153584101141163
62 384307168202282326
63 768614336404564651
64 1537228672809129302
65 3074457345618258603
66 6148914691236517206
67 12297829382473034411
68 24595658764946068822
69 49191317529892137643
70 98382635059784275286
71 196765270119568550571
72 393530540239137101142
73 787061080478274202283
74 1574122160956548404566
75 3148244321913096809131
76 6296488643826193618262
77 12592977287652387236523
78 25185954575304774473046
79 50371909150609548946091
80 100743818301219097892182
81 201487636602438195784363
82 402975273204876391568726
83 805950546409752783137451
84 1611901092819505566274902
85 3223802185639011132549803
86 6447604371278022265099606
87 12895208742556044530199211
88 25790417485112089060398422
89 51580834970224178120796843
90 103161669940448356241593686
91 206323339880896712483187371
92 412646679761793424966374742
93 825293359523586849932749483
94 1650586719047173699865498966
95 3301173438094347399730997931
96 6602346876188694799461995862
97 13204693752377389598923991723
98 26409387504754779197847983446
99 52818775009509558395695966891
100 105637550019019116791391933782