Rare numbers: Difference between revisions
Content added Content deleted
(added simple python implementation. will work on more complex python version next.) |
|||
Line 3,717: | Line 3,717: | ||
<lang langur>val .reverse = f toNumber join reverse split .n</lang> |
<lang langur>val .reverse = f toNumber join reverse split .n</lang> |
||
=={{header|Nim}}== |
|||
{{trans|Go}} |
|||
Translation of the second Go version, limited to 18 digits. |
|||
<lang Nim>import algorithm, math, strformat, times |
|||
type Llst = seq[seq[int]] |
|||
const |
|||
# Powers of 10. |
|||
P = block: |
|||
var p: array[19, int64] |
|||
p[0] = 1i64 |
|||
for i in 1..18: p[i] = 10 * p[i - 1] |
|||
p |
|||
# Digital root lookup array. |
|||
Drar = block: |
|||
var drar: array[19, int] |
|||
for i in 0..18: drar[i] = i shl 1 mod 9 |
|||
drar |
|||
var |
|||
d: seq[int] # permutation working slice |
|||
dac: seq[int] # running digital root slice |
|||
ac: seq[int64] # accumulator slice |
|||
pp: seq[int64] # coefficient slice that combines with digits of working slice |
|||
sr: seq[int64] # temporary list of squares used for building |
|||
var |
|||
odd = false # flag for odd number of digits |
|||
sum: int64 # calculated sum of terms (square candidate) |
|||
cn = 0 # solution counter |
|||
nd = 2 # number of digits |
|||
nd1 = nd - 1 # 'nd' helper |
|||
ln: int # previous value of 'n' (in recurse()) |
|||
dl: int # length of 'd' slice |
|||
func newIntSeq(f, t, s: int): seq[int] = |
|||
## Return a sequence of integers. |
|||
result = newSeq[int]((t - f) div s + 1) |
|||
var f = f |
|||
for i in 0..result.high: |
|||
result[i] = f |
|||
inc f, s |
|||
const |
|||
Tlo = @[0, 1, 4, 5, 6] # primary differences starting point |
|||
All = newIntSeq(-9, 9, 1) # all possible differences |
|||
Odl = newIntSeq(-9, 9, 2) # odd possible differences |
|||
Evl = newIntSeq(-8, 8, 2) # even possible differences |
|||
Thi = @[4, 5, 6, 9, 10, 11, 14, 15, 16] # primary sums starting point |
|||
Alh = newIntSeq(0, 18, 1) # all possible sums |
|||
Odh = newIntSeq(1, 17, 2) # odd possible sums |
|||
Evh = newIntSeq(0, 18, 2) # even possible sums |
|||
Ten = newIntSeq(0, 9, 1) # used for odd number of digits |
|||
Z = newIntSeq(0, 0, 1) # no difference, avoids generating a bunch of negative square candidates |
|||
T7 = @[-3, 7] # shortcut for low 5 |
|||
Nin = @[9] # shortcut for hi 10 |
|||
Tn = @[10] # shortcut for hi 0 (unused, unneeded) |
|||
T12 = @[2, 12] # shortcut for hi 5 |
|||
O11 = @[1, 11] # shortcut for hi 15 |
|||
Pos = @[0, 1, 4, 5, 6, 9] # shortcut for 2nd lo 0 |
|||
var |
|||
lul: Llst = @[Z, Odl, @[], @[], Evl, T7, Odl] # shortcut lookup lo primary |
|||
luh: Llst = @[Tn, Evh, @[], @[], Evh, T12, Odh, @[], @[], |
|||
Evh, Nin, Odh, @[], @[], Odh, O11, Evh] # shortcut lookup hi primary |
|||
l2l: Llst = @[Pos, @[], @[], @[], All, @[], All] # shortcut lookup lo secondary |
|||
l2h: Llst = @[@[], @[], @[], @[], Alh, @[], Alh, @[], @[], |
|||
@[], Alh, @[], @[], @[], Alh, @[], Alh] # shortcut lookup hi secondary |
|||
chTen: Llst = @[@[0, 2, 5, 8, 9], @[0, 3, 4, 6, 9], @[1, 4, 7, 8], |
|||
@[2, 3, 5, 8], @[0, 3, 6, 7, 9], @[1, 2, 4, 7], |
|||
@[2, 5, 6, 8], @[0, 1, 3, 6, 9], @[1, 4, 5, 7]] |
|||
chAH: Llst = @[@[0, 2, 5, 8, 9, 11, 14, 17, 18], @[0, 3, 4, 6, 9, 12, 13, 15, 18], |
|||
@[1, 4, 7, 8, 10, 13, 16, 17], @[2, 3, 5, 8, 11, 12, 14, 17], |
|||
@[0, 3, 6, 7, 9, 12, 15, 16, 18], @[1, 2, 4, 7, 10, 11, 13, 16], |
|||
@[2, 5, 6, 8, 11, 14, 15, 17], @[0, 1, 3, 6, 9, 10, 12, 15, 18], |
|||
@[1, 4, 5, 7, 10, 13, 14, 16]] |
|||
var lu, l2: Llst |
|||
func isr(s: int64): int64 {.inline.} = |
|||
## Return integer square root. |
|||
int64(sqrt(float(s))) |
|||
proc isRev(nd: int; f, r: int64): bool = |
|||
## Recursively determines whether 'r' is the reverse of 'f'. |
|||
let nd = nd - 1 |
|||
if f div P[nd] != r mod 10: return false |
|||
if nd < 1: return true |
|||
result = isRev(nd, f mod P[nd], r div 10) |
|||
proc recurseLE5(lst: Llst; lv: int) = |
|||
## Recursive function to evaluate the permutations, no shortcuts. |
|||
if lv == dl: # Check if on last stage of permutation. |
|||
sum = ac[lv - 1] |
|||
if sum > 0: |
|||
let rt = int64(sqrt(float(sum))) |
|||
if rt * rt == sum: sr.add sum |
|||
else: |
|||
for n in lst[lv]: # Set up next permutation. |
|||
d[lv] = n |
|||
if lv == 0: ac[0] = pp[0] * n |
|||
else: ac[lv] = ac[lv - 1] + pp[lv] * n # Update accumulated sum. |
|||
recurseLE5(lst, lv + 1) # Recursively call next level. |
|||
proc recursehi(lst: var Llst; lv: int) = |
|||
## Recursive function to evaluate the hi permutations. |
|||
## Shortcuts added to avoid generating many non-squares, digital root calc added. |
|||
let lv1 = lv - 1 |
|||
if lv == dl: # Check if on last stage of permutation. |
|||
sum = ac[lv1] |
|||
if (0x202021202030213 and (1 shl (sum and 63))) != 0: |
|||
# Test accumulated sum, append to result if square. |
|||
let rt = int64(sqrt(float64(sum))) |
|||
if rt * rt == sum: sr.add sum |
|||
else: |
|||
for n in lst[lv]: # Set up next permutation. |
|||
d[lv] = n |
|||
if lv == 0: |
|||
ac[0] = pp[0] * n |
|||
dac[0] = Drar[n] # Update accumulated sum and running dr. |
|||
else: |
|||
ac[lv] = ac[lv1] + pp[lv] * n |
|||
dac[lv] = dac[lv1] + Drar[n] |
|||
if dac[lv] > 8: dec dac[lv], 9 |
|||
case lv # Shortcuts to be performed on designated levels. |
|||
of 0: # Primary level: set shortcuts for secondary level. |
|||
ln = n |
|||
lst[1] = lu[ln] |
|||
lst[2] = l2[n] |
|||
of 1: # Secondary level: set shortcuts for tertiary level. |
|||
case ln # For sums. |
|||
of 5, 15: lst[2] = if n < 10: Evh else: Odh |
|||
of 9: lst[2] = if (n shr 1 and 1) == 0: Evh else: Odh |
|||
of 11: lst[2] = if (n shr 1 and 1) == 1: Evh else: Odh |
|||
else: discard |
|||
else: discard |
|||
if lv == dl - 2: |
|||
# Reduce last round according to dr calc. |
|||
lst[dl - 1] = if odd: chTen[dac[dl - 2]] else: chAH[dac[dl - 2]] |
|||
recursehi(lst, lv + 1) # Recursively call next level. |
|||
proc recurselo(lst: var Llst; lv: int) = |
|||
## Recursive function to evaluate the lo permutations. |
|||
## Shortcuts added to avoid generating many non-squares. |
|||
let lv1 = lv - 1 |
|||
if lv == dl: # Check if on last stage of permutation. |
|||
sum = ac[lv1] |
|||
if sum > 0: |
|||
let rt = int64(sqrt(float64(sum))) |
|||
if rt * rt == sum: sr.add sum |
|||
else: |
|||
for n in lst[lv]: # Set up next permutation. |
|||
d[lv] = n |
|||
if lv == 0: ac[0] = pp[0] * n |
|||
else: ac[lv] = ac[lv1] + pp[lv] * n # Update accumulated sum. |
|||
case lv # Shortcuts to be performed on designated levels. |
|||
of 0: # Primary level: set shortcuts for secondary level. |
|||
ln = n |
|||
lst[1] = lu[ln] |
|||
lst[2] = l2[n] |
|||
of 1: # Secondary level: set shortcuts for tertiary level. |
|||
case ln # For difs. |
|||
of 1: lst[2] = if ((n + 9) shr 1 and 1) == 0: Evl else: Odl |
|||
of 5: lst[2] = if n < 0: Evl else: Odl |
|||
else: discard |
|||
else: discard |
|||
recurselo(lst, lv + 1) # Recursively call next level. |
|||
proc listEm(lst: var Llst; plu, pl2: Llst): seq[int64] = |
|||
## Produces a list of candidate square numbers. |
|||
dl = lst.len |
|||
d = newSeq[int](dl) |
|||
sr.setLen(0) |
|||
lu = plu |
|||
l2 = pl2 |
|||
ac = newSeq[int64](dl) |
|||
dac = newSeq[int](dl) |
|||
pp = newSeq[int64](dl) |
|||
# Build coefficients array. |
|||
for i in 0..<dl: |
|||
pp[i] = if lst[0].len > 6: P[nd1 - i] + P[i] else: P[nd1 - i] - P[i] |
|||
# Call appropriate recursive function. |
|||
if nd <= 5: recurseLE5(lst, 0) |
|||
elif lst[0].len > 8: recursehi(lst, 0) |
|||
else: recurselo(lst, 0) |
|||
result = sr |
|||
proc reveal(lo, hi: openArray[int64]) = |
|||
## Reveal whether combining two lists of squares can produce a rare number. |
|||
var s: seq[string] # Temporary list of results. |
|||
for l in lo: |
|||
for h in hi: |
|||
let r = (h - l) shr 1 |
|||
let f = h - r # Generate all possible fwd & rev candidates from lists. |
|||
if isRev(nd, f, r): |
|||
s.add &"{f:20} {isr(h):11} {isr(l):10} " |
|||
s.sort() |
|||
if s.len > 0: |
|||
for t in s: |
|||
inc cn |
|||
let tt = if t != s[^1]: "\n" else: "" |
|||
stdout.write &"{cn:2} {t}{tt}" |
|||
else: |
|||
stdout.write &"{\"\":48}" |
|||
func formatTime(d: Duration): string = |
|||
var f = d.inMilliseconds |
|||
var s = f div 1000 |
|||
f = f mod 1000 |
|||
var m = s div 60 |
|||
s = s mod 60 |
|||
let h = m div 60 |
|||
m = m mod 60 |
|||
result = &"{h:02}:{m:02}:{s:02}.{f:03}" |
|||
var |
|||
lls: Llst = @[Tlo] |
|||
hls: Llst = @[Thi] |
|||
var bstart, tstart = now() |
|||
echo &"""nth {"forward":>19} {"rt.sum":>11} {"rt.dif":>10} digs {"block time":>11} {"total time":>13}""" |
|||
while nd <= 18: |
|||
if nd > 2: |
|||
if odd: |
|||
hls.add Ten |
|||
else: |
|||
lls.add All |
|||
hls[^1] = Alh |
|||
reveal(listEm(lls, lul, l2l), listEm(hls, luh, l2h)) |
|||
if not odd and nd > 5: |
|||
# Restore last element of hls, so that dr shortcut doesn't mess up next nd. |
|||
hls[^1] = Alh |
|||
let bTime = formatTime(now() - bstart) |
|||
let tTime = formatTime(now() - tstart) |
|||
echo &"{nd:2}: {bTime} {tTime}" |
|||
bstart = now() # Restart block timing. |
|||
nd1 = nd |
|||
inc nd |
|||
odd = not odd</lang> |
|||
{{out}} |
|||
<pre>nth forward rt.sum rt.dif digs block time total time |
|||
1 65 11 3 2: 00:00:00.000 00:00:00.000 |
|||
3: 00:00:00.000 00:00:00.000 |
|||
4: 00:00:00.000 00:00:00.000 |
|||
5: 00:00:00.000 00:00:00.000 |
|||
2 621770 836 738 6: 00:00:00.000 00:00:00.000 |
|||
7: 00:00:00.000 00:00:00.001 |
|||
8: 00:00:00.001 00:00:00.002 |
|||
3 281089082 23708 330 9: 00:00:00.002 00:00:00.005 |
|||
4 2022652202 63602 300 |
|||
5 2042832002 63602 6360 10: 00:00:00.005 00:00:00.010 |
|||
11: 00:00:00.040 00:00:00.051 |
|||
6 868591084757 1275175 333333 |
|||
7 872546974178 1320616 32670 |
|||
8 872568754178 1320616 33330 12: 00:00:00.066 00:00:00.117 |
|||
9 6979302951885 3586209 1047717 13: 00:00:00.486 00:00:00.603 |
|||
10 20313693904202 6368252 269730 |
|||
11 20313839704202 6368252 270270 |
|||
12 20331657922202 6368252 329670 |
|||
13 20331875722202 6368252 330330 |
|||
14 20333875702202 6368252 336330 |
|||
15 40313893704200 6368252 6330336 |
|||
16 40351893720200 6368252 6336336 14: 00:00:00.968 00:00:01.572 |
|||
17 200142385731002 20006998 69300 |
|||
18 204238494066002 20122102 1891560 |
|||
19 221462345754122 21045662 69300 |
|||
20 244062891224042 22011022 1908060 |
|||
21 245518996076442 22140228 921030 |
|||
22 248359494187442 22206778 1891560 |
|||
23 403058392434500 20211202 19940514 |
|||
24 441054594034340 22011022 19940514 |
|||
25 816984566129618 40421606 250800 15: 00:00:09.416 00:00:10.989 |
|||
26 2078311262161202 64030648 7529850 |
|||
27 2133786945766212 65272218 2666730 |
|||
28 2135568943984212 65272218 3267330 |
|||
29 2135764587964212 65272218 3326670 |
|||
30 2135786765764212 65272218 3333330 |
|||
31 4135786945764210 65272218 63333336 |
|||
32 6157577986646405 105849161 33333333 |
|||
33 6889765708183410 83866464 82133718 |
|||
34 8052956026592517 123312255 29999997 |
|||
35 8052956206592517 123312255 30000003 |
|||
36 8191154686620818 127950856 3299670 |
|||
37 8191156864620818 127950856 3300330 |
|||
38 8191376864400818 127950856 3366330 |
|||
39 8650327689541457 127246955 33299667 |
|||
40 8650349867341457 127246955 33300333 16: 00:00:18.483 00:00:29.472 |
|||
41 22542040692914522 212329862 333300 |
|||
42 67725910561765640 269040196 251135808 |
|||
43 86965750494756968 417050956 33000 17: 00:02:49.293 00:03:18.766 |
|||
44 225342456863243522 671330638 297000 |
|||
45 225342458663243522 671330638 303000 |
|||
46 225342478643243522 671330638 363000 |
|||
47 284684666566486482 754565658 30000 |
|||
48 284684868364486482 754565658 636000 |
|||
49 297128548234950692 770186978 32697330 |
|||
50 297128722852950692 770186978 32702670 |
|||
51 297148324656930692 770186978 33296670 |
|||
52 297148546434930692 770186978 33303330 |
|||
53 497168548234910690 770186978 633363336 |
|||
54 619431353040136925 1071943279 299667003 |
|||
55 619631153042134925 1071943279 300333003 |
|||
56 631688638047992345 1083968809 297302703 |
|||
57 633288858025996145 1083968809 302637303 |
|||
58 633488632647994145 1083968809 303296697 |
|||
59 653488856225994125 1083968809 363303363 |
|||
60 811865096390477018 1273828556 33030330 |
|||
61 865721270017296468 1315452006 32071170 |
|||
62 871975098681469178 1320582934 3303300 |
|||
63 898907259301737498 1339270086 64576740 18: 00:05:45.616 00:09:04.383</pre> |
|||
=={{header|Phix}}== |
=={{header|Phix}}== |