First perfect square in base n with n unique digits: Difference between revisions

Content added Content deleted
(Added Wren)
Line 3,768: Line 3,768:
28 9 58A3CKP3N4CQD7 -> 1023456CGJBIRQEDHP98KMOAN7FL 749593055 711.660s 1617.981s
28 9 58A3CKP3N4CQD7 -> 1023456CGJBIRQEDHP98KMOAN7FL 749593055 711.660s 1617.981s
Elasped time was 26.97 minutes</pre>Base29 seems to take an order of magnitude longer. I'm looking into some shortcuts.
Elasped time was 26.97 minutes</pre>Base29 seems to take an order of magnitude longer. I'm looking into some shortcuts.

=={{header|Wren}}==
{{trans|Go}}
{{libheader|Wren-big}}
{{libheader|Wren-math}}
{{libheader|Wren-fmt}}
Base 21 is as far as we can reasonably fly here though (unsurprisingly) base 20 takes a long time.
<lang ecmascript>import "/big" for BigInt
import "/math" for Nums
import "/fmt" for Conv, Fmt

var maxBase = 21
var minSq36 = "1023456789abcdefghijklmnopqrstuvwxyz"
var minSq36x = "10123456789abcdefghijklmnopqrstuvwxyz"

var containsAll = Fn.new { |sq, base|
var found = List.filled(maxBase, 0)
var le = sq.count
var reps = 0
for (r in sq) {
var d = r.bytes[0] - 48
if (d > 38) d = d - 39
found[d] = found[d] + 1
if (found[d] > 1) {
reps = reps + 1
if (le - reps < base) return false
}
}
return true
}

var sumDigits = Fn.new { |n, base|
var sum = BigInt.zero
while (n > 0) {
sum = sum + (n%base)
n = n/base
}
return sum
}

var digitalRoot = Fn.new { |n, base|
while (n > base - 1) n = sumDigits.call(n, base)
return n.toSmall
}

var minStart = Fn.new { |base|
var ms = minSq36[0...base]
var nn = BigInt.fromBaseString(ms, base)
var bdr = digitalRoot.call(nn, base)
var drs = []
var ixs = []
for (n in 1...2*base) {
nn = BigInt.new(n*n)
var dr = digitalRoot.call(nn, base)
if (dr == 0) dr = n * n
if (dr == bdr) ixs.add(n)
if (n < base && dr >= bdr) drs.add(dr)
}
var inc = 1
if (ixs.count >= 2 && base != 3) inc = ixs[1] - ixs[0]
if (drs.count == 0) return [ms, inc, bdr]
var min = Nums.min(drs)
var rd = min - bdr
if (rd == 0) return [ms, inc, bdr]
if (rd == 1) return [minSq36x[0..base], 1, bdr]
var ins = minSq36[rd]
return [(minSq36[0...rd] + ins + minSq36[rd..-1])[0..base], inc, bdr]
}

var start = System.clock
var n = 2
var k = 1
var base = 2
while (true) {
if (base == 2 || (n % base) != 0) {
var nb = BigInt.new(n)
var sq = nb.square.toBaseString(base)
if (containsAll.call(sq, base)) {
var ns = Conv.itoa(n, base)
var tt = System.clock - start
Fmt.print("Base $2d:$15s² = $-27s in $8.3fs", base, ns, sq, tt)
if (base == maxBase) break
base = base + 1
var res = minStart.call(base)
var ms = res[0]
var inc = res[1]
var bdr = res[2]
k = inc
var nn = BigInt.fromBaseString(ms, base)
nb = nn.isqrt
if (nb < n + 1) nb = BigInt.new(n+1)
if (k != 1) {
while (true) {
nn = nb.square
var dr = digitalRoot.call(nn, base)
if (dr == bdr) {
n = nb.toSmall - k
break
}
nb = nb.inc
}
} else {
n = nb.toSmall - k
}
}
}
n = n + k
}</lang>

{{out}}
<pre>
Base 2: 10² = 100 in 0.000s
Base 3: 22² = 2101 in 0.000s
Base 4: 33² = 3201 in 0.001s
Base 5: 243² = 132304 in 0.001s
Base 6: 523² = 452013 in 0.002s
Base 7: 1431² = 2450361 in 0.003s
Base 8: 3344² = 13675420 in 0.004s
Base 9: 11642² = 136802574 in 0.011s
Base 10: 32043² = 1026753849 in 0.011s
Base 11: 111453² = 1240a536789 in 0.044s
Base 12: 3966b9² = 124a7b538609 in 0.201s
Base 13: 3828943² = 10254773ca86b9 in 0.426s
Base 14: 3a9db7c² = 10269b8c57d3a4 in 0.501s
Base 15: 1012b857² = 102597bace836d4 in 0.651s
Base 16: 404a9d9b² = 1025648cfea37bd9 in 1.351s
Base 17: 423f82ga9² = 101246a89cgfb357ed in 10.534s
Base 18: 44b482cad² = 10236b5f8eg4ad9ch7 in 12.008s
Base 19: 1011b55e9a² = 10234dhbg7ci8f6a9e5 in 18.055s
Base 20: 49dgih5d3g² = 1024e7cdi3hb695fja8g in 696.567s
Base 21: 4c9he5fe27f² = 1023457dg9hi8j6b6kceaf in 735.738s
</pre>


=={{header|zkl}}==
=={{header|zkl}}==
Retrieved from "https://rosettacode.org/wiki/First_perfect_square_in_base_n_with_n_unique_digits"