Rare numbers: Difference between revisions

=={{header|Wren}}==

{{trans|Go}}

{{libheader|Wren-sort}}

{{libheader|Wren-fmt}}

{{libheader|Wren-date}}

A translation of Go's 'traditional' and 'turbo' versions.

Quite a tough task for the little bird which lacks the speed of its compiled, statically typed brethren. Also integer arithmetic is unreliable for numbers >= 2^53 which effectively limits us here to 15 digit rare numbers without resorting to BigInt which would be even slower.

===Traditional===

About 9.5 minutes to find the first 25 rare numbers.

<lang ecmascript>import "/sort" for Sort

import "/fmt" for Fmt

class Term {

construct new(coeff, ix1, ix2) {

_coeff = coeff

_ix1 = ix1

_ix2 = ix2

}

coeff { _coeff }

ix1 { _ix1 }

ix2 { _ix2 }

}

var maxDigits = 15

var toInt = Fn.new { |digits, reverse|

var sum = 0

if (!reverse) {

for (i in 0...digits.count) sum = sum*10 + digits[i]

} else {

for (i in digits.count-1..0) sum = sum*10 + digits[i]

}

return sum

}

var isSquare = Fn.new { |n|

var root = n.sqrt.floor

return root*root == n

}

var seq = Fn.new { |from, to, step|

var res = []

var i = from

while (i <= to) {

res.add(i)

i = i + step

}

return res

}

var start = System.clock

var pow = 1

System.print("Aggregate timings to process all numbers up to:")

// terms of (n-r) expression for number of digits from 2 to maxDigits

var allTerms = List.filled(maxDigits-1, null)

for (r in 2..maxDigits) {

var terms = []

pow = pow * 10

var pow1 = pow

var pow2 = 1

var i1 = 0

var i2 = r - 1

while (i1 < i2) {

terms.add(Term.new(pow1-pow2, i1, i2))

pow1 = (pow1/10).floor

pow2 = pow2 * 10

i1 = i1 + 1

i2 = i2 - 1

}

allTerms[r-2] = terms

}

// map of first minus last digits for 'n' to pairs giving this value

var fml = {

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

var dmd = {}

for (i in 0...100) {

var a = [(i/10).floor, i%10]

var d = a[0] - a[1]

if (dmd[d]) {

dmd[d].add(a)

} else {

dmd[d] = [a]

}

}

var fl = [0, 1, 4, 6]

var dl = seq.call(-9, 9, 1) // all differences

var zl = [0] // zero differences only

var el = seq.call(-8, 8, 2) // even differences only

var ol = seq.call(-9, 9, 2) // odd differences only

var il = seq.call(0, 9, 1)

var rares = []

var lists = List.filled(4, null)

for (i in 0..3) lists[i] = [[fl[i]]]

var digits = []

var count = 0

// Recursive closure to generate (n+r) candidates from (n-r) candidates

// and hence find Rare numbers with a given number of digits.

var fnpr

fnpr = Fn.new { |cand, di, dis, indices, nmr, nd, level|

if (level == dis.count) {

digits[indices[0][0]] = fml[cand[0]][di[0]][0]

digits[indices[0][1]] = fml[cand[0]][di[0]][1]

var le = di.count

if (nd%2 == 1) {

le = le - 1

digits[(nd/2).floor] = di[le]

}

var i = 0

for (d in di[1...le]) {

digits[indices[i+1][0]] = dmd[cand[i+1]][d][0]

digits[indices[i+1][1]] = dmd[cand[i+1]][d][1]

i = i + 1

}

var r = toInt.call(digits, true)

var npr = nmr + 2*r

if (!isSquare.call(npr)) return

count = count + 1

Fmt.write(" R/N $2d:", count)

var ms = ((System.clock - start)*1000).round

Fmt.write(" $,7d ms", ms)

var n = toInt.call(digits, false)

Fmt.print(" ($,d)", n)

rares.add(n)

} else {

for (num in dis[level]) {

di[level] = num

System.write("") // guards against VM recursion bug

fnpr.call(cand, di, dis, indices, nmr, nd, level+1)

}

}

}

// Recursive closure to generate (n-r) candidates with a given number of digits.

var fnmr

fnmr = Fn.new { |cand, list, indices, nd, level|

if (level == list.count) {

var nmr = 0

var nmr2 = 0

var i = 0

for (t in allTerms[nd-2]) {

if (cand[i] >= 0) {

nmr = nmr + t.coeff*cand[i]

} else {

nmr2 = nmr2 - t.coeff*cand[i]

if (nmr >= nmr2) {

nmr = nmr - nmr2

nmr2 = 0

} else {

nmr2 = nmr2 - nmr

nmr = 0

}

}

i = i + 1

}

if (nmr2 >= nmr) return

nmr = nmr - nmr2

if (!isSquare.call(nmr)) return

var dis = []

dis.add(seq.call(0, fml[cand[0]].count-1, 1))

for (i in 1...cand.count) {

dis.add(seq.call(0, dmd[cand[i]].count-1, 1))

}

if (nd%2 == 1) dis.add(il)

var di = List.filled(dis.count, 0)

fnpr.call(cand, di, dis, indices, nmr, nd, 0)

} else {

for (num in list[level]) {

cand[level] = num

System.write("") // guards against VM recursion bug

fnmr.call(cand, list, indices, nd, level+1)

}

}

}

for (nd in 2..maxDigits) {

digits = List.filled(nd, 0)

if (nd == 4) {

lists[0].add(zl)

lists[1].add(ol)

lists[2].add(el)

lists[3].add(ol)

} else if(allTerms[nd-2].count > lists[0].count) {

for (i in 0..3) lists[i].add(dl)

}

var indices = []

for (t in allTerms[nd-2]) indices.add([t.ix1, t.ix2])

for (list in lists) {

var cand = List.filled(list.count, 0)

fnmr.call(cand, list, indices, nd, 0)

}

var ms = ((System.clock - start)*1000).round

Fmt.print(" $2s digits: $,7d ms", nd, ms)

}

Sort.quick(rares)

Fmt.print("\nThe rare numbers with up to $d digits are:\n", maxDigits)

var i = 0

for (rare in rares) {

Fmt.print(" $2d: $,21d", i+1, rare)

i = i + 1

}</lang>

{{out}}

<pre>

Aggregate timings to process all numbers up to:

R/N 1: 0 ms (65)

2 digits: 0 ms

3 digits: 0 ms

4 digits: 0 ms

5 digits: 0 ms

R/N 2: 3 ms (621,770)

6 digits: 3 ms

7 digits: 8 ms

8 digits: 54 ms

R/N 3: 56 ms (281,089,082)

9 digits: 77 ms

R/N 4: 80 ms (2,022,652,202)

R/N 5: 355 ms (2,042,832,002)

10 digits: 1,044 ms

11 digits: 1,742 ms

R/N 6: 4,892 ms (872,546,974,178)

R/N 7: 5,270 ms (872,568,754,178)

R/N 8: 11,318 ms (868,591,084,757)

12 digits: 15,797 ms

R/N 9: 20,673 ms (6,979,302,951,885)

13 digits: 28,328 ms

R/N 10: 79,833 ms (20,313,693,904,202)

R/N 11: 81,291 ms (20,313,839,704,202)

R/N 12: 101,982 ms (20,331,657,922,202)

R/N 13: 104,914 ms (20,331,875,722,202)

R/N 14: 113,507 ms (20,333,875,702,202)

R/N 15: 287,986 ms (40,313,893,704,200)

R/N 16: 290,036 ms (40,351,893,720,200)

14 digits: 340,736 ms

R/N 17: 342,140 ms (200,142,385,731,002)

R/N 18: 345,178 ms (221,462,345,754,122)

R/N 19: 384,744 ms (816,984,566,129,618)

R/N 20: 405,787 ms (245,518,996,076,442)

R/N 21: 409,179 ms (204,238,494,066,002)

R/N 22: 410,135 ms (248,359,494,187,442)

R/N 23: 414,341 ms (244,062,891,224,042)

R/N 24: 511,124 ms (403,058,392,434,500)

R/N 25: 514,313 ms (441,054,594,034,340)

15 digits: 565,126 ms

The rare numbers with up to 15 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

</pre>

===Turbo===

Ruffles the feathers a little with a time 5 times quicker than the 'traditional' version.

<lang ecmascript>import "/sort" for Sort

import "/fmt" for Fmt

import "/date" for Date

class Z2 {

construct new(value, hasValue) {

_value = value

_hasValue = hasValue

}

value { _value }

hasValue { _hasValue }

}

var Pow10 = List.filled(16, 0)

var init = Fn.new {

Pow10[0] = 1

for (i in 1..15) Pow10[i] = 10 * Pow10[i-1]

}

var acc = 0

var bs = List.filled(100000, false)

var L

var H

var izRev

izRev = Fn.new { |n, i, g|

if ((i/Pow10[n-1]).floor != g%10) return false

if (n < 2) return true

System.write("") // guards against VM recursion bug

return izRev.call(n-1, i%Pow10[n-1], (g/10).floor)

}

var fG = Fn.new { |n, start, end, reset, step|

var i = step * start

var g = step * end

var e = step * reset

return Fn.new {

while (i < g) {

acc = acc + step

i = i + step

return Z2.new(acc, true)

}

i = e

acc = acc - (g - e)

return n.call()

}

}

class ZP {

construct new(n, g) {

_n = n

_g = g

}

n { _n }

g { _g }

}

class NLH {

construct new(e) {

var even = []

var odd = []

var n = e.n

var g = e.g

var i = n.call()

while (i.hasValue) {

for (p in g) {

var ng = p[0]

var gg = p[1]

if (ng > 0 || i.value > 0) {

var w = ng*Pow10[4] + gg + i.value

var ws = w.sqrt.floor

if (ws*ws == w) {

if (w%2 == 0) {

even.add(w)

} else {

odd.add(w)

}

}

}

}

i = n.call()

}

_even = even

_odd = odd

}

even { _even }

odd { _odd }

}

var makeL = Fn.new { |n|

var g = List.filled((n/2).floor - 3, null)

g[0] = Fn.new { Z2.new(0, false) }

var i = 1

while (i < (n/2).floor - 3) {

var s = -9

if (i == (n/2).floor - 4) s = -10

var l = Pow10[n-i-4] - Pow10[i+3]

acc = acc + l*s

g[i] = fG.call(g[i-1], s, 9, -9, l)

i = i + 1

}

var g0 = 0

var g1 = 0

var g2 = 0

var g3 = 0

var l0 = Pow10[n-5]

var l1 = Pow10[n-6]

var l2 = Pow10[n-7]

var l3 = Pow10[n-8]

var f = Fn.new {

var w = []

while (g0 < 7) {

var nn = g3*l3 + g2*l2 + g1*l1 + g0*l0

var gg = -1000*g3 - 100*g2 - 10*g1 - g0

if (g3 < 9) {

g3 = g3 + 1

} else {

g3 = -9

if (g2 < 9) {

g2 = g2 + 1

} else {

g2 = -9

if (g1 < 9) {

g1 = g1 + 1

} else {

g1 = -9

if (g0 == 1) g0 = 3

g0 = g0 + 1

}

}

}

if (bs[(Pow10[10]+gg)%10000]) w.add([nn, gg])

}

return w

}

return ZP.new(g[(n/2).floor-4], f.call())

}

var makeH = Fn.new { |n|

acc = -(Pow10[(n/2).floor] + Pow10[((n-1)/2).floor])

var g = List.filled(((n+1)/2).floor - 3, null)

g[0] = Fn.new { Z2.new(0, false) }

var i = 1

while (i < (n/2).floor - 3) {

var j = 0

if (i == ((n+1)/2).floor - 3) j = -1

g[i] = fG.call(g[i-1], j, 18, 0, Pow10[n-i-4]+Pow10[i+3])

if (n%2 == 1) {

g[((n+1)/2).floor-4] = fG.call(g[(n/2).floor-4], -1, 9, 0, 2*Pow10[(n/2).floor])

}

i = i + 1

}

var g0 = 4

var g1 = 0

var g2 = 0

var g3 = 0

var l0 = Pow10[n-5]

var l1 = Pow10[n-6]

var l2 = Pow10[n-7]

var l3 = Pow10[n-8]

var f = Fn.new {

var w = []

while (g0 < 17) {

var nn = g3*l3 + g2*l2 + g1*l1 + g0*l0

var gg = 1000*g3 + 100*g2 + 10*g1 + g0

if (g3 < 18) {

g3 = g3 + 1

} else {

g3 = 0

if (g2 < 18) {

g2 = g2 + 1

} else {

g2 = 0

if (g1 < 18) {

g1 = g1 + 1

} else {

g1 = 0

if (g0 == 6 || g0 == 9) g0 = g0 + 3

g0 = g0 + 1

}

}

}

if (bs[gg%10000]) w.add([nn, gg])

}

return w

}

return ZP.new(g[((n+1)/2).floor-4], f.call())

}

var rare = Fn.new { |n|

acc = 0

for (g in 0...10000) bs[(g*g)%10000] = true

L = NLH.new(makeL.call(n))

H = NLH.new(makeH.call(n))

var rares = []

for (l in L.even) {

for (h in H.even) {

var r = ((h - l)/2).floor

var z = h - r

if (izRev.call(n, r, z)) rares.add(z)

}

}

for (l in L.odd) {

for (h in H.odd) {

var r = ((h - l)/2).floor

var z = h - r

if (izRev.call(n, r, z)) rares.add(z)

}

}

if (rares.count > 0) Sort.quick(rares)

return rares

}

// Formats time in form hh:mm:ss.fff (i.e. millisecond precision).

var formatTime = Fn.new { |d|

var ms = (d * 1000).round

var tm = Date.fromNumber(ms)

Date.default = Date.isoTime + "|.|ttt"

return tm.toString

}

var bStart = System.clock // block time

var tStart = bStart // total time

init.call()

var nth = 3 // i.e. count of rare numbers < 10 digits

System.print("nth rare number digs block time total time")

for (nd in 10..15) {

var rares = rare.call(nd)

if (rares.count > 0) {

var i = 0

for (r in rares) {

nth = nth + 1

var t = ""

if (i < rares.count - 1) t = "\n"

Fmt.write("$2d $,21d$s", nth, r, t)

i = i + 1

}

} else {

Fmt.write("$26s", "")

}

var fbTime = formatTime.call(System.clock - bStart)

var ftTime = formatTime.call(System.clock - tStart)

Fmt.print(" $2d: $s $s", nd, fbTime, ftTime)

bStart = System.clock // restart block timing

}</lang>

{{out}}

<pre>

nth rare number digs block time total time

4 2,022,652,202

5 2,042,832,002 10: 00:00:00.084 00:00:00.084

11: 00:00:00.262 00:00:00.346

6 868,591,084,757

7 872,546,974,178

8 872,568,754,178 12: 00:00:00.714 00:00:01.060

9 6,979,302,951,885 13: 00:00:04.601 00:00:05.662

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:13.764 00:00:19.426

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:01:34.206 00:01:53.632

</pre>