Find palindromic numbers in both binary and ternary bases: Difference between revisions

=={{header|Nim}}==

{{trans|Ada}}

<lang Nim>import bitops, strformat, times

#---------------------------------------------------------------------------------------------------

func isPal2(k: uint64; digitCount: Natural): bool =

## Return true if the "digitCount" + 1 bits of "k" form a palindromic number.

for i in 0..digitCount:

if k.testBit(i) != k.testBit(digitCount - i):

return false

result = true

#---------------------------------------------------------------------------------------------------

func reverseNumber(k: uint64): uint64 =

## Return the reverse number of "n".

var p = k

while p > 0:

result += 2 * result + p mod 3

p = p div 3

#---------------------------------------------------------------------------------------------------

func toBase2(n: uint64): string =

## Return the string representation of "n" in base 2.

var n = n

while true:

result.add(chr(ord('0') + (n and 1)))

n = n shr 1

if n == 0: break

#---------------------------------------------------------------------------------------------------

func toBase3(n: uint64): string =

## Return the string representation of "n" in base 3.

var n = n

while true:

result.add(chr(ord('0') + n mod 3))

n = n div 3

if n == 0: break

#---------------------------------------------------------------------------------------------------

proc print(n: uint64) =

## Print the value in bases 10, 2 and 3.

echo &"{n:>18} {n.toBase2():^59} {n.toBase3():^41}"

#---------------------------------------------------------------------------------------------------

proc findPal23() =

## Find the seven first palindromic numbers in binary and ternary bases.

var p3 = 1u64

var countPal = 1

print(0)

for p in 0..31:

while (3 * p3 + 1) * p3 < 1u64 shl (2 * p):

p3 *= 3

let bound = 1u64 shl (2 * p) div (3 * p3)

for k in max(p3 div 3, bound) .. min(2 * bound, p3 - 1):

let n = (3 * k + 1) * p3 + reverseNumber(k)

if isPal2(n, 2 * p):

print(n)

inc countPal

if countPal == 7:

return

#———————————————————————————————————————————————————————————————————————————————————————————————————

let t0 = cpuTime()

findPal23()

echo fmt"\nTime: {cpuTime() - t0:.2f}s"</lang>

{{out}}

<pre> 0 0 0

1 1 1

6643 1100111110011 100010001

1422773 101011011010110110101 2200021200022

5415589 10100101010001010100101 101012010210101

90396755477 1010100001100000100010000011000010101 22122022220102222022122

381920985378904469 10101001100110110110001110011011001110001101101100110010101 2112200222001222121212221002220022112

Time: 4.89s</pre>