Rare numbers: Difference between revisions

← Older editNewer edit →
Content deleted Content added
Added Visual Basic .NET version
PureFox (talk | contribs)
9,493 edits
→‎{{header|Go}}: Now using uint64 to find all rare numbers with up to 19 digits.
Line 404: Line 404:


type term struct {
type term struct {
coeff int64
coeff uint64
ix1, ix2 int8
ix1, ix2 int8
}
}


const maxDigits = 18
const maxDigits = 19


func toInt64(digits []int8, reverse bool) int64 {
func toUint64(digits []int8, reverse bool) uint64 {
sum := int64(0)
sum := uint64(0)
if !reverse {
if !reverse {
for i := 0; i < len(digits); i++ {
for i := 0; i < len(digits); i++ {
sum = sum*10 + int64(digits[i])
sum = sum*10 + uint64(digits[i])
}
}
} else {
} else {
for i := len(digits) - 1; i >= 0; i-- {
for i := len(digits) - 1; i >= 0; i-- {
sum = sum*10 + int64(digits[i])
sum = sum*10 + uint64(digits[i])
}
}
}
}
Line 424: Line 424:
}
}


func isSquare(n int64) bool {
func isSquare(n uint64) bool {
if 0x202021202030213&(1<<(n&63)) != 0 {
if 0x202021202030213&(1<<(n&63)) != 0 {
root := int64(math.Sqrt(float64(n)))
root := uint64(math.Sqrt(float64(n)))
return root*root == n
return root*root == n
}
}
Line 440: Line 440:
}
}


func commatize(n int64) string {
func commatize(n uint64) string {
s := fmt.Sprintf("%d", n)
s := fmt.Sprintf("%d", n)
le := len(s)
le := len(s)
Line 451: Line 451:
func main() {
func main() {
start := time.Now()
start := time.Now()
pow := int64(1)
pow := uint64(1)
fmt.Println("Aggregate timings to process all numbers up to:")
fmt.Println("Aggregate timings to process all numbers up to:")
// terms of (n-r) expression for number of digits from 2 to maxDigits
// terms of (n-r) expression for number of digits from 2 to maxDigits
Line 458: Line 458:
var terms []term
var terms []term
pow *= 10
pow *= 10
pow1, pow2 := pow, int64(1)
pow1, pow2 := pow, uint64(1)
for i1, i2 := int8(0), int8(r-1); i1 < i2; i1, i2 = i1+1, i2-1 {
for i1, i2 := int8(0), int8(r-1); i1 < i2; i1, i2 = i1+1, i2-1 {
terms = append(terms, term{pow1 - pow2, i1, i2})
terms = append(terms, term{pow1 - pow2, i1, i2})
Line 486: Line 486:
ol := seq(-9, 9, 2) // odd differences only
ol := seq(-9, 9, 2) // odd differences only
il := seq(0, 9, 1)
il := seq(0, 9, 1)
var rares []int64
var rares []uint64
lists := make([][][]int8, 4)
lists := make([][][]int8, 4)
for i, f := range fl {
for i, f := range fl {
Line 496: Line 496:
// Recursive closure to generate (n+r) candidates from (n-r) candidates
// Recursive closure to generate (n+r) candidates from (n-r) candidates
// and hence find Rare numbers with a given number of digits.
// and hence find Rare numbers with a given number of digits.
var fnpr func(cand, di []int8, dis [][]int8, indices [][2]int8, nmr int64, nd, level int)
var fnpr func(cand, di []int8, dis [][]int8, indices [][2]int8, nmr uint64, nd, level int)
fnpr = func(cand, di []int8, dis [][]int8, indices [][2]int8, nmr int64, nd, level int) {
fnpr = func(cand, di []int8, dis [][]int8, indices [][2]int8, nmr uint64, nd, level int) {
if level == len(dis) {
if level == len(dis) {
digits[indices[0][0]] = fml[cand[0]][di[0]][0]
digits[indices[0][0]] = fml[cand[0]][di[0]][0]
Line 510: Line 510:
digits[indices[i+1][1]] = dmd[cand[i+1]][d][1]
digits[indices[i+1][1]] = dmd[cand[i+1]][d][1]
}
}
r := toInt64(digits, true)
r := toUint64(digits, true)
npr := nmr + 2*r
npr := nmr + 2*r
if !isSquare(npr) {
if !isSquare(npr) {
Line 517: Line 517:
count++
count++
fmt.Printf(" R/N %2d:", count)
fmt.Printf(" R/N %2d:", count)
fmt.Printf(" %9s ms", commatize(time.Since(start).Milliseconds()))
ms := uint64(time.Since(start).Milliseconds())
n := toInt64(digits, false)
fmt.Printf(" %9s ms", commatize(ms))
n := toUint64(digits, false)
fmt.Printf(" (%s)\n", commatize(n))
fmt.Printf(" (%s)\n", commatize(n))
rares = append(rares, n)
rares = append(rares, n)
Line 533: Line 534:
fnmr = func(cand []int8, list [][]int8, indices [][2]int8, nd, level int) {
fnmr = func(cand []int8, list [][]int8, indices [][2]int8, nd, level int) {
if level == len(list) {
if level == len(list) {
nmr := int64(0)
nmr := uint64(0)
for i, t := range allTerms[nd-2] {
for i, t := range allTerms[nd-2] {
nmr += t.coeff * int64(cand[i])
nmr += t.coeff * uint64(cand[i])
}
}
if nmr <= 0 || !isSquare(nmr) {
if nmr == 0 || !isSquare(nmr) {
return
return
}
}
Line 578: Line 579:
fnmr(cand, list, indices, nd, 0)
fnmr(cand, list, indices, nd, 0)
}
}
fmt.Printf(" %2d digits: %9s ms\n", nd, commatize(time.Since(start).Milliseconds()))
ms := uint64(time.Since(start).Milliseconds())
fmt.Printf(" %2d digits: %9s ms\n", nd, commatize(ms))
}
}


Line 584: Line 586:
fmt.Printf("\nThe rare numbers with up to %d digits are:\n", maxDigits)
fmt.Printf("\nThe rare numbers with up to %d digits are:\n", maxDigits)
for i, rare := range rares {
for i, rare := range rares {
fmt.Printf(" %2d: %23s\n", i+1, commatize(rare))
fmt.Printf(" %2d: %25s\n", i+1, commatize(rare))
}
}
}</lang>
}</lang>


{{output}}
{{output}}
Timings are for an Intel Core i7-8565U machine with 32GB RAM running Go 1.13.1 on Ubuntu 18.04.
Timings are for an Intel Core i7-8565U machine with 32GB RAM running Go 1.13.3 on Ubuntu 18.04.
<pre style="height:126ex;overflow:scroll">
<pre>
Aggregate timings to process all numbers up to:
Aggregate timings to process all numbers up to:
R/N 1: 0 ms (65)
R/N 1: 0 ms (65)
Line 597: Line 599:
4 digits: 0 ms
4 digits: 0 ms
5 digits: 0 ms
5 digits: 0 ms
R/N 2: 1 ms (621,770)
R/N 2: 0 ms (621,770)
6 digits: 1 ms
6 digits: 0 ms
7 digits: 2 ms
7 digits: 0 ms
8 digits: 15 ms
8 digits: 3 ms
R/N 3: 15 ms (281,089,082)
R/N 3: 3 ms (281,089,082)
9 digits: 20 ms
9 digits: 4 ms
R/N 4: 20 ms (2,022,652,202)
R/N 4: 4 ms (2,022,652,202)
R/N 5: 59 ms (2,042,832,002)
R/N 5: 26 ms (2,042,832,002)
10 digits: 99 ms
10 digits: 65 ms
11 digits: 137 ms
11 digits: 102 ms
R/N 6: 361 ms (872,546,974,178)
R/N 6: 322 ms (872,546,974,178)
R/N 7: 389 ms (872,568,754,178)
R/N 7: 349 ms (872,568,754,178)
R/N 8: 738 ms (868,591,084,757)
R/N 8: 693 ms (868,591,084,757)
12 digits: 888 ms
12 digits: 841 ms
R/N 9: 1,130 ms (6,979,302,951,885)
R/N 9: 1,088 ms (6,979,302,951,885)
13 digits: 1,446 ms
13 digits: 1,403 ms
R/N 10: 4,990 ms (20,313,693,904,202)
R/N 10: 5,113 ms (20,313,693,904,202)
R/N 11: 5,058 ms (20,313,839,704,202)
R/N 11: 5,179 ms (20,313,839,704,202)
R/N 12: 6,475 ms (20,331,657,922,202)
R/N 12: 6,647 ms (20,331,657,922,202)
R/N 13: 6,690 ms (20,331,875,722,202)
R/N 13: 6,862 ms (20,331,875,722,202)
R/N 14: 7,293 ms (20,333,875,702,202)
R/N 14: 7,476 ms (20,333,875,702,202)
R/N 15: 16,685 ms (40,313,893,704,200)
R/N 15: 16,972 ms (40,313,893,704,200)
R/N 16: 16,818 ms (40,351,893,720,200)
R/N 16: 17,108 ms (40,351,893,720,200)
14 digits: 17,855 ms
14 digits: 18,147 ms
R/N 17: 17,871 ms (200,142,385,731,002)
R/N 17: 18,164 ms (200,142,385,731,002)
R/N 18: 18,079 ms (221,462,345,754,122)
R/N 18: 18,362 ms (221,462,345,754,122)
R/N 19: 20,774 ms (816,984,566,129,618)
R/N 19: 20,924 ms (816,984,566,129,618)
R/N 20: 22,155 ms (245,518,996,076,442)
R/N 20: 22,226 ms (245,518,996,076,442)
R/N 21: 22,350 ms (204,238,494,066,002)
R/N 21: 22,409 ms (204,238,494,066,002)
R/N 22: 22,413 ms (248,359,494,187,442)
R/N 22: 22,470 ms (248,359,494,187,442)
R/N 23: 22,687 ms (244,062,891,224,042)
R/N 23: 22,729 ms (244,062,891,224,042)
R/N 24: 26,698 ms (403,058,392,434,500)
R/N 24: 26,510 ms (403,058,392,434,500)
R/N 25: 26,905 ms (441,054,594,034,340)
R/N 25: 26,707 ms (441,054,594,034,340)
15 digits: 27,932 ms
15 digits: 27,685 ms
R/N 26: 77,599 ms (2,133,786,945,766,212)
R/N 26: 76,878 ms (2,133,786,945,766,212)
R/N 27: 96,932 ms (2,135,568,943,984,212)
R/N 27: 95,916 ms (2,135,568,943,984,212)
R/N 28: 99,869 ms (8,191,154,686,620,818)
R/N 28: 98,634 ms (8,191,154,686,620,818)
R/N 29: 102,401 ms (8,191,156,864,620,818)
R/N 29: 100,959 ms (8,191,156,864,620,818)
R/N 30: 103,535 ms (2,135,764,587,964,212)
R/N 30: 102,003 ms (2,135,764,587,964,212)
R/N 31: 105,255 ms (2,135,786,765,764,212)
R/N 31: 104,178 ms (2,135,786,765,764,212)
R/N 32: 109,232 ms (8,191,376,864,400,818)
R/N 32: 107,850 ms (8,191,376,864,400,818)
R/N 33: 122,372 ms (2,078,311,262,161,202)
R/N 33: 120,650 ms (2,078,311,262,161,202)
R/N 34: 148,814 ms (8,052,956,026,592,517)
R/N 34: 146,724 ms (8,052,956,026,592,517)
R/N 35: 153,226 ms (8,052,956,206,592,517)
R/N 35: 151,440 ms (8,052,956,206,592,517)
R/N 36: 185,251 ms (8,650,327,689,541,457)
R/N 36: 182,434 ms (8,650,327,689,541,457)
R/N 37: 187,467 ms (8,650,349,867,341,457)
R/N 37: 184,492 ms (8,650,349,867,341,457)
R/N 38: 189,163 ms (6,157,577,986,646,405)
R/N 38: 186,621 ms (6,157,577,986,646,405)
R/N 39: 217,112 ms (4,135,786,945,764,210)
R/N 39: 214,493 ms (4,135,786,945,764,210)
R/N 40: 230,719 ms (6,889,765,708,183,410)
R/N 40: 227,622 ms (6,889,765,708,183,410)
16 digits: 231,583 ms
16 digits: 228,463 ms
R/N 41: 236,505 ms (86,965,750,494,756,968)
R/N 41: 233,839 ms (86,965,750,494,756,968)
R/N 42: 237,391 ms (22,542,040,692,914,522)
R/N 42: 234,699 ms (22,542,040,692,914,522)
R/N 43: 351,728 ms (67,725,910,561,765,640)
R/N 43: 351,294 ms (67,725,910,561,765,640)
17 digits: 360,678 ms
17 digits: 360,264 ms
R/N 44: 392,403 ms (284,684,666,566,486,482)
R/N 44: 394,105 ms (284,684,666,566,486,482)
R/N 45: 513,738 ms (225,342,456,863,243,522)
R/N 45: 517,309 ms (225,342,456,863,243,522)
R/N 46: 558,603 ms (225,342,458,663,243,522)
R/N 46: 562,610 ms (225,342,458,663,243,522)
R/N 47: 653,047 ms (225,342,478,643,243,522)
R/N 47: 658,489 ms (225,342,478,643,243,522)
R/N 48: 718,569 ms (284,684,868,364,486,482)
R/N 48: 724,844 ms (284,684,868,364,486,482)
R/N 49: 1,087,602 ms (871,975,098,681,469,178)
R/N 49: 1,102,934 ms (871,975,098,681,469,178)
R/N 50: 1,763,809 ms (865,721,270,017,296,468)
R/N 50: 1,784,186 ms (865,721,270,017,296,468)
R/N 51: 1,779,059 ms (297,128,548,234,950,692)
R/N 51: 1,799,704 ms (297,128,548,234,950,692)
R/N 52: 1,787,466 ms (297,128,722,852,950,692)
R/N 52: 1,808,108 ms (297,128,722,852,950,692)
R/N 53: 1,888,803 ms (811,865,096,390,477,018)
R/N 53: 1,910,757 ms (811,865,096,390,477,018)
R/N 54: 1,940,347 ms (297,148,324,656,930,692)
R/N 54: 1,963,039 ms (297,148,324,656,930,692)
R/N 55: 1,965,331 ms (297,148,546,434,930,692)
R/N 55: 1,989,078 ms (297,148,546,434,930,692)
R/N 56: 2,273,287 ms (898,907,259,301,737,498)
R/N 56: 2,300,661 ms (898,907,259,301,737,498)
R/N 57: 2,657,073 ms (631,688,638,047,992,345)
R/N 57: 2,684,798 ms (631,688,638,047,992,345)
R/N 58: 2,682,636 ms (619,431,353,040,136,925)
R/N 58: 2,710,279 ms (619,431,353,040,136,925)
R/N 59: 2,948,725 ms (619,631,153,042,134,925)
R/N 59: 2,977,798 ms (619,631,153,042,134,925)
R/N 60: 3,011,962 ms (633,288,858,025,996,145)
R/N 60: 3,041,540 ms (633,288,858,025,996,145)
R/N 61: 3,077,937 ms (633,488,632,647,994,145)
R/N 61: 3,107,298 ms (633,488,632,647,994,145)
R/N 62: 3,928,545 ms (653,488,856,225,994,125)
R/N 62: 3,969,243 ms (653,488,856,225,994,125)
R/N 63: 4,195,016 ms (497,168,548,234,910,690)
R/N 63: 4,236,641 ms (497,168,548,234,910,690)
18 digits: 4,445,897 ms
18 digits: 4,488,380 ms
R/N 64: 4,562,327 ms (2,551,755,006,254,571,552)
R/N 65: 4,580,772 ms (2,702,373,360,882,732,072)
R/N 66: 4,828,482 ms (2,825,378,427,312,735,282)
R/N 67: 4,849,194 ms (8,066,308,349,502,036,608)
R/N 68: 5,065,098 ms (2,042,401,829,204,402,402)
R/N 69: 5,108,808 ms (2,420,424,089,100,600,242)
R/N 70: 5,218,730 ms (8,320,411,466,598,809,138)
R/N 71: 5,506,140 ms (8,197,906,905,009,010,818)
R/N 72: 5,534,376 ms (2,060,303,819,041,450,202)
R/N 73: 5,709,174 ms (8,200,756,128,308,135,597)
R/N 74: 5,947,856 ms (6,531,727,101,458,000,045)
R/N 75: 6,451,016 ms (6,988,066,446,726,832,640)
19 digits: 6,514,522 ms


The rare numbers with up to 18 digits are:
The rare numbers with up to 19 digits are:
1: 65
1: 65
2: 621,770
2: 621,770
3: 281,089,082
3: 281,089,082
4: 2,022,652,202
4: 2,022,652,202
5: 2,042,832,002
5: 2,042,832,002
6: 868,591,084,757
6: 868,591,084,757
7: 872,546,974,178
7: 872,546,974,178
8: 872,568,754,178
8: 872,568,754,178
9: 6,979,302,951,885
9: 6,979,302,951,885
10: 20,313,693,904,202
10: 20,313,693,904,202
11: 20,313,839,704,202
11: 20,313,839,704,202
12: 20,331,657,922,202
12: 20,331,657,922,202
13: 20,331,875,722,202
13: 20,331,875,722,202
14: 20,333,875,702,202
14: 20,333,875,702,202
15: 40,313,893,704,200
15: 40,313,893,704,200
16: 40,351,893,720,200
16: 40,351,893,720,200
17: 200,142,385,731,002
17: 200,142,385,731,002
18: 204,238,494,066,002
18: 204,238,494,066,002
19: 221,462,345,754,122
19: 221,462,345,754,122
20: 244,062,891,224,042
20: 244,062,891,224,042
21: 245,518,996,076,442
21: 245,518,996,076,442
22: 248,359,494,187,442
22: 248,359,494,187,442
23: 403,058,392,434,500
23: 403,058,392,434,500
24: 441,054,594,034,340
24: 441,054,594,034,340
25: 816,984,566,129,618
25: 816,984,566,129,618
26: 2,078,311,262,161,202
26: 2,078,311,262,161,202
27: 2,133,786,945,766,212
27: 2,133,786,945,766,212
28: 2,135,568,943,984,212
28: 2,135,568,943,984,212
29: 2,135,764,587,964,212
29: 2,135,764,587,964,212
30: 2,135,786,765,764,212
30: 2,135,786,765,764,212
31: 4,135,786,945,764,210
31: 4,135,786,945,764,210
32: 6,157,577,986,646,405
32: 6,157,577,986,646,405
33: 6,889,765,708,183,410
33: 6,889,765,708,183,410
34: 8,052,956,026,592,517
34: 8,052,956,026,592,517
35: 8,052,956,206,592,517
35: 8,052,956,206,592,517
36: 8,191,154,686,620,818
36: 8,191,154,686,620,818
37: 8,191,156,864,620,818
37: 8,191,156,864,620,818
38: 8,191,376,864,400,818
38: 8,191,376,864,400,818
39: 8,650,327,689,541,457
39: 8,650,327,689,541,457
40: 8,650,349,867,341,457
40: 8,650,349,867,341,457
41: 22,542,040,692,914,522
41: 22,542,040,692,914,522
42: 67,725,910,561,765,640
42: 67,725,910,561,765,640
43: 86,965,750,494,756,968
43: 86,965,750,494,756,968
44: 225,342,456,863,243,522
44: 225,342,456,863,243,522
45: 225,342,458,663,243,522
45: 225,342,458,663,243,522
46: 225,342,478,643,243,522
46: 225,342,478,643,243,522
47: 284,684,666,566,486,482
47: 284,684,666,566,486,482
48: 284,684,868,364,486,482
48: 284,684,868,364,486,482
49: 297,128,548,234,950,692
49: 297,128,548,234,950,692
50: 297,128,722,852,950,692
50: 297,128,722,852,950,692
51: 297,148,324,656,930,692
51: 297,148,324,656,930,692
52: 297,148,546,434,930,692
52: 297,148,546,434,930,692
53: 497,168,548,234,910,690
53: 497,168,548,234,910,690
54: 619,431,353,040,136,925
54: 619,431,353,040,136,925
55: 619,631,153,042,134,925
55: 619,631,153,042,134,925
56: 631,688,638,047,992,345
56: 631,688,638,047,992,345
57: 633,288,858,025,996,145
57: 633,288,858,025,996,145
58: 633,488,632,647,994,145
58: 633,488,632,647,994,145
59: 653,488,856,225,994,125
59: 653,488,856,225,994,125
60: 811,865,096,390,477,018
60: 811,865,096,390,477,018
61: 865,721,270,017,296,468
61: 865,721,270,017,296,468
62: 871,975,098,681,469,178
62: 871,975,098,681,469,178
63: 898,907,259,301,737,498
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>
</pre>


Retrieved from "https://rosettacode.org/wiki/Rare_numbers"