Talk:Rare numbers: Difference between revisions
Content added Content deleted
(→21+ digit rare numbers: Responded to Nigel.) |
|||
Line 506: | Line 506: | ||
::::To reliably go any further than this would require the use of big integers (unpleasant and relatively slow in Go) as signed 64 bit integers have a 19 digit maximum. It might be possible to use unsigned 64 bit integers (20 digit maximum) though this would require some fancy footwork to deal with negative numbers and subtraction. So I think that's my lot now :) --[[User:PureFox|PureFox]] ([[User talk:PureFox|talk]]) 20:04, 2 October 2019 (UTC) |
::::To reliably go any further than this would require the use of big integers (unpleasant and relatively slow in Go) as signed 64 bit integers have a 19 digit maximum. It might be possible to use unsigned 64 bit integers (20 digit maximum) though this would require some fancy footwork to deal with negative numbers and subtraction. So I think that's my lot now :) --[[User:PureFox|PureFox]] ([[User talk:PureFox|talk]]) 20:04, 2 October 2019 (UTC) |
||
== Tweaks, Go (Turbo) == |
|||
Still some performance hiding in there... |
|||
Skipping combinations 2 and 3 for the differences, and stopping at 6 instead of 9. |
|||
Since no square can end in the digit 2 or 3, these can be skipped safely. 6 is the highest possible |
|||
difference, so stopping at 6 is OK. |
|||
Skipping combinations 0 through 3, 7 through 9, and 12 through 14 on the sums. |
|||
Since lowest possible first digit of the rare number is 2, and the sum must be greater than the rare number, |
|||
and digits 2 and 3 cannot be the last digits of the sum, 4 is the lowest possible last digit of the sum. |
|||
Also, no square can end in digits 7 or 8, so combinations starting with 7, 8, 12, & 13 can be eliminated. |
|||
Removing combination 9 & 14 is cheating, however no solution up to 19 digits depends on the sum being a |
|||
square containing the combination 9 or 14 as the first/last digit. |
|||
<lang go>package main |
|||
import ( |
|||
"fmt" |
|||
"math" |
|||
"sort" |
|||
"time" |
|||
) |
|||
type ( |
|||
z1 func() z2 |
|||
z2 struct { |
|||
value int64 |
|||
hasValue bool |
|||
} |
|||
) |
|||
var pow10 [19]int64 |
|||
func init() { |
|||
pow10[0] = 1 |
|||
for i := 1; i < 19; i++ { |
|||
pow10[i] = 10 * pow10[i-1] |
|||
} |
|||
} |
|||
func izRev(n int, i, g uint64) bool { |
|||
if i/uint64(pow10[n-1]) != g%10 { |
|||
return false |
|||
} |
|||
if n < 2 { |
|||
return true |
|||
} |
|||
return izRev(n-1, i%uint64(pow10[n-1]), g/10) |
|||
} |
|||
func fG(n z1, start, end, reset int, step int64, l *int64) z1 { |
|||
i, g, e := step*int64(start), step*int64(end), step*int64(reset) |
|||
return func() z2 { |
|||
for i < g { |
|||
*l += step |
|||
i += step |
|||
return z2{*l, true} |
|||
} |
|||
i = e |
|||
*l -= (g - e) |
|||
return n() |
|||
} |
|||
} |
|||
type nLH struct{ even, odd []uint64 } |
|||
type zp struct { |
|||
n z1 |
|||
g [][2]int64 |
|||
} |
|||
func newNLH(e zp) nLH { |
|||
var even, odd []uint64 |
|||
n, g := e.n, e.g |
|||
for i := n(); i.hasValue; i = n() { |
|||
for _, p := range g { |
|||
ng, gg := p[0], p[1] |
|||
if (ng > 0) || (i.value > 0) { |
|||
w := uint64(ng*pow10[4] + gg + i.value) |
|||
ws := uint64(math.Sqrt(float64(w))) |
|||
if ws*ws == w { |
|||
if w%2 == 0 { |
|||
even = append(even, w) |
|||
} else { |
|||
odd = append(odd, w) |
|||
} |
|||
} |
|||
} |
|||
} |
|||
} |
|||
return nLH{even, odd} |
|||
} |
|||
func makeL(n int) zp { |
|||
g := make([]z1, n/2-3) |
|||
g[0] = func() z2 { return z2{} } |
|||
for i := 1; i < n/2-3; i++ { |
|||
s := -9 |
|||
if i == n/2-4 { |
|||
s = -10 |
|||
} |
|||
l := pow10[n-i-4] - pow10[i+3] |
|||
acc += l * int64(s) |
|||
g[i] = fG(g[i-1], s, 9, -9, l, &acc) |
|||
} |
|||
var g0, g1, g2, g3 int64 |
|||
l0, l1, l2, l3 := pow10[n-5], pow10[n-6], pow10[n-7], pow10[n-8] |
|||
f := func() [][2]int64 { |
|||
var w [][2]int64 |
|||
for g0 < 7 { |
|||
nn := g3*l3 + g2*l2 + g1*l1 + g0*l0 |
|||
gg := -1000*g3 - 100*g2 - 10*g1 - g0 |
|||
if g3 < 9 { |
|||
g3++ |
|||
} else { |
|||
g3 = -9 |
|||
if g2 < 9 { |
|||
g2++ |
|||
} else { |
|||
g2 = -9 |
|||
if g1 < 9 { |
|||
g1++ |
|||
} else { |
|||
g1 = -9 |
|||
g0 == 1 { g0 += 2 } |
|||
g0++ |
|||
} |
|||
} |
|||
} |
|||
if bs[(pow10[10]+gg)%10000] { |
|||
w = append(w, [2]int64{nn, gg}) |
|||
} |
|||
} |
|||
return w |
|||
} |
|||
return zp{g[n/2-4], f()} |
|||
} |
|||
func makeH(n int) zp { |
|||
acc = -(pow10[n/2] + pow10[(n-1)/2]) |
|||
g := make([]z1, (n+1)/2-3) |
|||
g[0] = func() z2 { return z2{} } |
|||
for i := 1; i < n/2-3; i++ { |
|||
j := 0 |
|||
if i == (n+1)/2-3 { |
|||
j = -1 |
|||
} |
|||
g[i] = fG(g[i-1], j, 18, 0, pow10[n-i-4]+pow10[i+3], &acc) |
|||
if n%2 == 1 { |
|||
g[(n+1)/2-4] = fG(g[n/2-4], -1, 9, 0, 2*pow10[n/2], &acc) |
|||
} |
|||
} |
|||
g0 := int64(4) |
|||
var g1, g2, g3 int64 |
|||
l0, l1, l2, l3 := pow10[n-5], pow10[n-6], pow10[n-7], pow10[n-8] |
|||
f := func() [][2]int64 { |
|||
var w [][2]int64 |
|||
for g0 < 17 { |
|||
nn := g3*l3 + g2*l2 + g1*l1 + g0*l0 |
|||
gg := 1000*g3 + 100*g2 + 10*g1 + g0 |
|||
if g3 < 18 { |
|||
g3++ |
|||
} else { |
|||
g3 = 0 |
|||
if g2 < 18 { |
|||
g2++ |
|||
} else { |
|||
g2 = 0 |
|||
if g1 < 18 { |
|||
g1++ |
|||
} else { |
|||
g1 = 0 |
|||
switch g0 {case 6, 9: g0 += 3 } |
|||
g0++ |
|||
} |
|||
} |
|||
} |
|||
if bs[gg%10000] { |
|||
w = append(w, [2]int64{nn, gg}) |
|||
} |
|||
} |
|||
return w |
|||
} |
|||
return zp{g[(n+1)/2-4], f()} |
|||
} |
|||
var ( |
|||
acc int64 |
|||
bs = make([]bool, 10000) |
|||
L, H nLH |
|||
) |
|||
func rare(n int) []uint64 { |
|||
acc = 0 |
|||
for g := 0; g < 10000; g++ { |
|||
bs[(g*g)%10000] = true |
|||
} |
|||
L = newNLH(makeL(n)) |
|||
H = newNLH(makeH(n)) |
|||
var rares []uint64 |
|||
for _, l := range L.even { |
|||
for _, h := range H.even { |
|||
r := (h - l) / 2 |
|||
z := h - r |
|||
if izRev(n, r, z) { |
|||
rares = append(rares, z) |
|||
} |
|||
} |
|||
} |
|||
for _, l := range L.odd { |
|||
for _, h := range H.odd { |
|||
r := (h - l) / 2 |
|||
z := h - r |
|||
if izRev(n, r, z) { |
|||
rares = append(rares, z) |
|||
} |
|||
} |
|||
} |
|||
if len(rares) > 0 { |
|||
sort.Slice(rares, func(i, j int) bool { |
|||
return rares[i] < rares[j] |
|||
}) |
|||
} |
|||
return rares |
|||
} |
|||
// Formats time in form hh:mm:ss.fff (i.e. millisecond precision). |
|||
func formatTime(d time.Duration) string { |
|||
f := d.Milliseconds() |
|||
s := f / 1000 |
|||
f %= 1000 |
|||
m := s / 60 |
|||
s %= 60 |
|||
h := m / 60 |
|||
m %= 60 |
|||
return fmt.Sprintf("%02d:%02d:%02d.%03d", h, m, s, f) |
|||
} |
|||
func commatize(n uint64) string { |
|||
s := fmt.Sprintf("%d", n) |
|||
le := len(s) |
|||
for i := le - 3; i >= 1; i -= 3 { |
|||
s = s[0:i] + "," + s[i:] |
|||
} |
|||
return s |
|||
} |
|||
func main() { |
|||
bStart := time.Now() // block time |
|||
tStart := bStart // total time |
|||
nth := 3 // i.e. count of rare numbers < 10 digits |
|||
fmt.Println("nth rare number digs block time total time") |
|||
for nd := 10; nd <= 19; nd++ { |
|||
rares := rare(nd) |
|||
if len(rares) > 0 { |
|||
for i, r := range rares { |
|||
nth++ |
|||
t := "" |
|||
if i < len(rares)-1 { |
|||
t = "\n" |
|||
} |
|||
fmt.Printf("%2d %25s%s", nth, commatize(r), t) |
|||
} |
|||
} else { |
|||
fmt.Printf("%29s", "") |
|||
} |
|||
fbTime := formatTime(time.Since(bStart)) |
|||
ftTime := formatTime(time.Since(tStart)) |
|||
fmt.Printf(" %2d: %s %s\n", nd, fbTime, ftTime) |
|||
bStart = time.Now() // restart block timing |
|||
} |
|||
}</lang> |
|||
{{out}} |
|||
Results on the core i7-7700 @ 3.6Ghz. |
|||
<pre style="height:64ex;overflow:scroll">nth rare number digs block time total time |
|||
4 2,022,652,202 |
|||
5 2,042,832,002 10: 00:00:00.001 00:00:00.001 |
|||
11: 00:00:00.006 00:00:00.008 |
|||
6 868,591,084,757 |
|||
7 872,546,974,178 |
|||
8 872,568,754,178 12: 00:00:00.015 00:00:00.024 |
|||
9 6,979,302,951,885 13: 00:00:00.098 00:00:00.123 |
|||
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 14: 00:00:00.269 00:00:00.392 |
|||
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 15: 00:00:01.810 00:00:02.203 |
|||
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 16: 00:00:05.122 00:00:07.325 |
|||
41 22,542,040,692,914,522 |
|||
42 67,725,910,561,765,640 |
|||
43 86,965,750,494,756,968 17: 00:00:33.461 00:00:40.787 |
|||
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 18: 00:01:37.823 00:02:18.611 |
|||
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 19: 00:12:22.226 00:14:40.838</pre> |
|||
== 21+ digit rare numbers == |
== 21+ digit rare numbers == |