Anonymous user
Rare numbers: Difference between revisions
→{{header|Nim}}
(added simple python implementation. will work on more complex python version next.) |
|||
Line 3,717:
<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}}==
| |||