Iterated digits squaring: Difference between revisions
Add BQN
(Iterated digits squaring en QBasic) |
(Add BQN) |
||
Line 316:
<pre>1..100000000 => 85744333</pre>
=={{header|BQN}}==
A simple solution is to compute all square-digit sums in the desired range as an addition table, then repeatedly select from this list using itself as an index so that all values that end at 1 converge (those that reach 89 will find some point in the cycle, but not always the same one).
<lang bqn> +´1↓1≠ ⊏˜⍟(⌈2⋆⁼≠) ⥊+⌜´6⥊<ט↕10
856929</lang>
It will take a lot of memory and many seconds to compute the count under 1e8 this way. The following program computes the count for numbers below <code>10⋆𝕩</code> by using dynamic programming to determine how many numbers have each possible digit sum. Then it finds the fate of each number in this greatly reduced set. This gives an exact result for inputs up to 16, taking a fraction of a millisecond for each.
<lang bqn>DigSq ← {
d ← ט ↕10 # Digit values
m ← 1+81×2⌈𝕩 # One plus maximum digit sum
c ← (+´ d ⥊⟜0⊸»¨ <)⍟𝕩 m↑⥊1 # Count of numbers having each sum
s ← m ↑ ⥊ d +⌜⍟(⌈10⋆⁼m) 0 # Sum for each sum
e ← 1≠⊏˜⍟(⌈2⋆⁼≠)s # Which sums end at 89
¯1 +´ c×e # Total up; subtract 1 to exclude 0
}</lang>
<lang bqn> >⋈⟜DigSq¨ 1+↕16
┌─
╵ 1 7
2 80
3 857
4 8558
5 85623
6 856929
7 8581146
8 85744333
9 854325192
10 8507390852
11 84908800643
12 850878696414
13 8556721999130
14 86229146720315
15 869339034137667
16 8754780882739336
┘</lang>
=={{header|C}}==
| |||