Strange numbers: Difference between revisions

=={{header|Nim}}==

Our program finds the strange numbers with a given number of digits. Filtering is done afterwards. It consumes a lot of memory but is able to find the result in less than a second on our small laptop.

<lang Nim>import algorithm, sequtils

const PrimeDigits = [2, 3, 5, 7]

type

Digit = 0..9

DigitSeq = seq[Digit]

func toInt(s: DigitSeq): int =

## Convert a sequence of digits to an int.

for d in s:

result = 10 * result + d

proc findStrangeNumbers(ndigits: Positive): seq[int] =

## Return the list of strange numbers with "ndigits" digits.

var list: seq[DigitSeq] = toSeq(1..9).mapIt(@[Digit it]) # Starting digits.

for _ in 2..ndigits:

var newList: seq[DigitSeq] # List with one more digit.

for dseq in list:

let last = dseq[^1]

for p in PrimeDigits:

if last - p >= 0:

newList.add dseq & (last - p)

if last + p <= 9:

newList.add dseq & (last + p)

list = move(newList) # "newList" becomes the current list.

result = list.map(toInt)

var result = sorted(findStrangeNumbers(3).filterIt(it < 500))

echo "Found ", result.len, " strange numbers between 101 and 499."

for i, n in result:

stdout.write n, if (i + 1) mod 15 == 0: '\n' else: ' '

echo()

result = findStrangeNumbers(10).filterIt(it div 1_000_000_000 == 1)

echo "\nFound ", result.len, " strange numbers with 10 digits and starting with 1."</lang>

{{out}}

<pre>Found 87 strange numbers between 101 and 499.

130 131 135 136 138 141 142 146 147 149 161 163 164 168 169

181 183 185 186 202 203 205 207 241 242 246 247 249 250 252

253 257 258 270 272 274 275 279 292 294 296 297 302 303 305

307 313 314 316 318 350 352 353 357 358 361 363 364 368 369

381 383 385 386 413 414 416 418 420 424 425 427 429 461 463

464 468 469 470 472 474 475 479 492 494 496 497

Found 853423 strange numbers with 10 digits and starting with 1.</pre>