Rare numbers: Difference between revisions
→{{header|Julia}}
(→{{header|Go}}: Bug fix, results unaffected.) |
|||
Line 782:
=={{header|Julia}}==
{{trans|Go}}
Timings are on a 2.9 GHz i5 processor under Windows 10.
<lang julia>using Formatting, Printf
struct Term
coeff::UInt64
ix1::Int8
ix2::Int8
end
function
return reverse ? foldr((i, j) -> i + 10j, UInt64.(dgits)) :
foldl((i, j) -> 10i + j, UInt64.(dgits))
end
function issquare(n)
if 0x202021202030213 & (1 << (UInt64(n) & 63)) != 0
root =
end
end
seq(from, to, step) = Int8.(collect(from:step:to))
commatize(n::Integer) = format(n, commas=true)
const verbose = true
const count = [0]
"""
Recursive closure to generate (n+r) candidates from (n-r) candidates
and hence find Rare numbers with a given number of digits.
"""
function fnpr(cand, di, dis, indices, nmr, nd, level, dgits, fml, dmd, start, rares, il)
if level == length(dis)
dgits[indices[1][1] + 1] = fml[cand[1]][di[1] + 1][1]
dgits[indices[1][2] + 1] = fml[cand[1]][di[1] + 1][2]
le = length(di)
if nd % 2 == 1
le -= 1
dgits[nd ÷ 2 + 1] = di[le + 1]
end
for (i, d) in enumerate(di[2:le])
dgits[indices[i+1][1] + 1] = dmd[cand[i+1]][d + 1][1]
dgits[indices[i+1][2] + 1] = dmd[cand[i+1]][d + 1][2]
end
r = toUInt64(dgits, true)
npr = nmr + 2 * r
!issquare(npr) && return
count[1] += 1
verbose && @printf(" R/N %2d:", count[1])
!verbose && print("$count rares\b\b\b\b\b\b\b\b\b")
ms = UInt64(time() * 1000 - start)
verbose && @printf(" %9s ms", commatize(Int(ms)))
n = toUInt64(dgits, false)
verbose && @printf(" (%s)\n", commatize(BigInt(n)))
push!(rares, n)
else
for num in dis[level + 1]
di[level + 1] = num
fnpr(cand, di, dis, indices, nmr, nd, level + 1, dgits, fml, dmd, start, rares, il)
end
end
end # function fnpr
# Recursive closure to generate (n-r) candidates with a given number of digits.
# var fnmr func(cand []int8, list [][]int8, indices [][2]int8, nd, level int)
function fnmr(cand, list, indices, nd, level, allterms, fml, dmd, dgits, start, rares, il)
if level == length(list)
nmr, nmr2 = zero(UInt64), zero(UInt64)
for (i, t) in enumerate(allterms[nd - 1])
if cand[i] >= 0
nmr += t.coeff * UInt64(cand[i])
else
nmr2 += t.coeff * UInt64(-cand[i])
if nmr >= nmr2
nmr -= nmr2
nmr2 = zero(nmr2)
else
nmr2 -= nmr
nmr = zero(nmr)
end
end
end
nmr2 >= nmr && return
nmr -= nmr2
!issquare(nmr) && return
dis = [[seq(0, Int8(length(fml[cand[1]]) - 1), 1)] ;
[seq(0, Int8(length(dmd[c]) - 1), 1) for c in cand[2:end]]]
isodd(nd) && push!(dis, il)
di = zeros(Int8, length(dis))
fnpr(cand, di, dis, indices, nmr, nd, 0, dgits, fml, dmd, start, rares, il)
else
for num in list[level + 1]
cand[level + 1] = num
fnmr(cand, list, indices, nd, level + 1, allterms, fml, dmd, dgits, start, rares, il)
end
end
end # function fnmr
function findrare(maxdigits = 19)
start = time() * 1000.0
pow = one(UInt64)
verbose && println("Aggregate timings to process all numbers up to:")
# terms of (n-r) expression for number of digits from 2 to maxdigits
allterms = Vector{Vector{Term}}()
for r in 2:maxdigits
terms = Term[]
pow *= 10
pow1, pow2, i1, i2 = pow, one(UInt64), zero(Int8), Int8(r - 1)
while i1 < i2
push!(terms, Term(pow1 - pow2, i1, i2))
pow1, pow2, i1, i2 = pow1 ÷ 10, pow2 * 10, i1 + 1, i2 - 1
end
push!(allterms, terms)
end
# map of first minus last digits for 'n' to pairs giving this value
fml = Dict(
0 => [2 => 2, 8 => 8],
1 => [6 => 5, 8 => 7],
4 => [4 => 0],
6 => [6 => 0, 8 => 2],
)
# map of other digit differences for 'n' to pairs giving this value
dmd = Dict{Int8, Vector{Vector{Int8}}}()
for i in 0:99
a = [Int8(i ÷ 10), Int8(i % 10)]
d = a[1] - a[2]
v = get!(dmd, d, [])
push!(v, a)
end
fl = Int8[0, 1, 4, 6]
dl = seq(-9, 9, 1) # all differences
zl = Int8[0] # zero differences only
el = seq(-8, 8, 2) # even differences only
ol = seq(-9, 9, 2) # odd differences only
il = seq(0, 9, 1)
rares = UInt64[]
lists = [[[f]] for f in fl]
dgits = Int8[]
count[1] = 0
for nd = 2:maxdigits
dgits = zeros(Int8, nd)
if nd == 4
push!(lists[1], zl)
push!(lists[2], ol)
push!(lists[3], el)
push!(lists[4], ol)
elseif length(allterms[nd - 1]) > length(lists[1])
for i in 1:4
push!(lists[i], dl)
end
end
indices = Vector{Vector{Int8}}()
for t in allterms[nd - 1]
push!(indices, Int8[t.ix1, t.ix2])
end
for list in lists
cand = zeros(Int8, length(list))
fnmr(cand, list, indices, nd, 0, allterms, fml, dmd, dgits, start, rares, il)
end
ms = UInt64(time() * 1000 - start)
verbose && @printf(" %2d digits: %9s ms\n", nd, commatize(Int(ms)))
end
sort!(rares)
@printf("\nThe rare numbers with up to %d digits are:\n", maxdigits)
for (i, rare) in enumerate(rares)
@printf(" %2d: %25s\n", i, commatize(BigInt(rare)))
end
end # findrare function
findrare()
</lang>{{out}}
<pre>
Aggregate timings to process all numbers up to:
R/N 1: 5 ms (65)
2 digits: 132 ms
3 digits: 133 ms
4 digits: 134 ms
5 digits: 134 ms
R/N 2: 135 ms (621,770)
6 digits: 135 ms
7 digits: 136 ms
8 digits: 140 ms
R/N 3: 141 ms (281,089,082)
9 digits: 143 ms
R/N 4: 144 ms (2,022,652,202)
R/N 5: 168 ms (2,042,832,002)
10 digits: 209 ms
11 digits: 251 ms
R/N 6: 443 ms (872,546,974,178)
R/N 7: 467 ms (872,568,754,178)
R/N 8: 773 ms (868,591,084,757)
12 digits: 919 ms
R/N 9: 1,178 ms (6,979,302,951,885)
13 digits: 1,510 ms
R/N 10: 4,662 ms (20,313,693,904,202)
R/N 11: 4,722 ms (20,313,839,704,202)
R/N 12: 6,028 ms (20,331,657,922,202)
R/N 13: 6,223 ms (20,331,875,722,202)
R/N 14: 6,753 ms (20,333,875,702,202)
R/N 15: 15,475 ms (40,313,893,704,200)
R/N 16: 15,594 ms (40,351,893,720,200)
14 digits: 16,749 ms
R/N 17: 16,772 ms (200,142,385,731,002)
R/N 18: 17,006 ms (221,462,345,754,122)
R/N 19: 20,027 ms (816,984,566,129,618)
R/N 20: 21,669 ms (245,518,996,076,442)
R/N 21: 21,895 ms (204,238,494,066,002)
R/N 22: 21,974 ms (248,359,494,187,442)
R/N 23: 22,302 ms (244,062,891,224,042)
R/N 24: 27,158 ms (403,058,392,434,500)
R/N 25: 27,405 ms (441,054,594,034,340)
15 digits: 28,744 ms
R/N 26: 79,350 ms (2,133,786,945,766,212)
R/N 27: 99,360 ms (2,135,568,943,984,212)
R/N 28: 102,426 ms (8,191,154,686,620,818)
R/N 29: 105,135 ms (8,191,156,864,620,818)
R/N 30: 106,334 ms (2,135,764,587,964,212)
R/N 31: 108,038 ms (2,135,786,765,764,212)
R/N 32: 112,142 ms (8,191,376,864,400,818)
R/N 33: 125,607 ms (2,078,311,262,161,202)
R/N 34: 154,417 ms (8,052,956,026,592,517)
R/N 35: 159,075 ms (8,052,956,206,592,517)
R/N 36: 192,323 ms (8,650,327,689,541,457)
R/N 37: 194,651 ms (8,650,349,867,341,457)
R/N 38: 196,344 ms (6,157,577,986,646,405)
R/N 39: 227,492 ms (4,135,786,945,764,210)
R/N 40: 244,502 ms (6,889,765,708,183,410)
16 digits: 245,658 ms
R/N 41: 251,178 ms (86,965,750,494,756,968)
R/N 42: 252,157 ms (22,542,040,692,914,522)
R/N 43: 382,883 ms (67,725,910,561,765,640)
17 digits: 393,371 ms
R/N 44: 427,555 ms (284,684,666,566,486,482)
R/N 45: 549,740 ms (225,342,456,863,243,522)
R/N 46: 594,392 ms (225,342,458,663,243,522)
R/N 47: 688,221 ms (225,342,478,643,243,522)
R/N 48: 753,385 ms (284,684,868,364,486,482)
R/N 49: 1,108,538 ms (871,975,098,681,469,178)
R/N 50: 1,770,255 ms (865,721,270,017,296,468)
R/N 51: 1,785,243 ms (297,128,548,234,950,692)
R/N 52: 1,793,571 ms (297,128,722,852,950,692)
R/N 53: 1,892,872 ms (811,865,096,390,477,018)
R/N 54: 1,941,208 ms (297,148,324,656,930,692)
R/N 55: 1,964,502 ms (297,148,546,434,930,692)
R/N 56: 2,267,616 ms (898,907,259,301,737,498)
R/N 57: 2,677,207 ms (631,688,638,047,992,345)
R/N 58: 2,702,836 ms (619,431,353,040,136,925)
R/N 59: 2,960,274 ms (619,631,153,042,134,925)
R/N 60: 3,019,846 ms (633,288,858,025,996,145)
R/N 61: 3,084,695 ms (633,488,632,647,994,145)
R/N 62: 3,924,801 ms (653,488,856,225,994,125)
R/N 63: 4,229,162 ms (497,168,548,234,910,690)
18 digits: 4,563,375 ms
R/N 64: 4,643,118 ms (2,551,755,006,254,571,552)
R/N 65: 4,662,645 ms (2,702,373,360,882,732,072)
R/N 66: 4,925,324 ms (2,825,378,427,312,735,282)
R/N 67: 4,947,368 ms (8,066,308,349,502,036,608)
R/N 68: 5,170,716 ms (2,042,401,829,204,402,402)
R/N 69: 5,216,832 ms (2,420,424,089,100,600,242)
R/N 70: 5,329,680 ms (8,320,411,466,598,809,138)
R/N 71: 5,634,991 ms (8,197,906,905,009,010,818)
R/N 72: 5,665,799 ms (2,060,303,819,041,450,202)
R/N 73: 5,861,019 ms (8,200,756,128,308,135,597)
R/N 74: 6,136,091 ms (6,531,727,101,458,000,045)
R/N 75: 6,770,242 ms (6,988,066,446,726,832,640)
19 digits: 6,846,705 ms
The rare numbers with up to 19 digits are:
1: 65
2: 621,770
3: 281,089,082
4: 2,022,652,202
5: 2,042,832,002
6: 868,591,084,757
7: 872,546,974,178
8: 872,568,754,178
9: 6,979,302,951,885
10: 20,313,693,904,202
11: 20,313,839,704,202
12: 20,331,657,922,202
13: 20,331,875,722,202
14: 20,333,875,702,202
15: 40,313,893,704,200
16: 40,351,893,720,200
17: 200,142,385,731,002
18: 204,238,494,066,002
19: 221,462,345,754,122
20: 244,062,891,224,042
21: 245,518,996,076,442
22: 248,359,494,187,442
23: 403,058,392,434,500
24: 441,054,594,034,340
25: 816,984,566,129,618
26: 2,078,311,262,161,202
27: 2,133,786,945,766,212
28: 2,135,568,943,984,212
29: 2,135,764,587,964,212
30: 2,135,786,765,764,212
31: 4,135,786,945,764,210
32: 6,157,577,986,646,405
33: 6,889,765,708,183,410
34: 8,052,956,026,592,517
35: 8,052,956,206,592,517
36: 8,191,154,686,620,818
37: 8,191,156,864,620,818
38: 8,191,376,864,400,818
39: 8,650,327,689,541,457
40: 8,650,349,867,341,457
41: 22,542,040,692,914,522
42: 67,725,910,561,765,640
43: 86,965,750,494,756,968
44: 225,342,456,863,243,522
45: 225,342,458,663,243,522
46: 225,342,478,643,243,522
47: 284,684,666,566,486,482
48: 284,684,868,364,486,482
49: 297,128,548,234,950,692
50: 297,128,722,852,950,692
51: 297,148,324,656,930,692
52: 297,148,546,434,930,692
53: 497,168,548,234,910,690
54: 619,431,353,040,136,925
55: 619,631,153,042,134,925
56: 631,688,638,047,992,345
57: 633,288,858,025,996,145
58: 633,488,632,647,994,145
59: 653,488,856,225,994,125
60: 811,865,096,390,477,018
61: 865,721,270,017,296,468
62: 871,975,098,681,469,178
63: 898,907,259,301,737,498
64: 2,042,401,829,204,402,402
65: 2,060,303,819,041,450,202
66: 2,420,424,089,100,600,242
67: 2,551,755,006,254,571,552
68: 2,702,373,360,882,732,072
69: 2,825,378,427,312,735,282
70: 6,531,727,101,458,000,045
71: 6,988,066,446,726,832,640
72: 8,066,308,349,502,036,608
73: 8,197,906,905,009,010,818
74: 8,200,756,128,308,135,597
75: 8,320,411,466,598,809,138
</pre>
| |||