Niven Number Computing Speed

Transcribed from the printed issue; not yet reviewed. Read it in the PDF of the issue, page 118

In his interesting article in Vector Vol.14 No.2, pp 121–124, Josef De Kerf notes that, so far, no algorithm has been found to calculate a given Niven number F(N) from N. I may of course be wrong but this seems to me to be a problem comparable with that of finding an algorithm to compute the Nth prime; i.e. there may little chance of eventual success.

A partial answer to the question of finding a faster algorithm may be to note the ease with which sums of digits can be found en bloc, so to speak, by repeated application of sum tables. Using J3 on a (Pentium 233) computer with 64MB RAM, I can find the digit sums for the first million integers in less than half a second. With these data, the Niven numbers can be identified in about 3 seconds. Beyond one million, the number of numbers being handled becomes so large that the swap file plays an increasing role, slowing the process down, leading to ‘out of memory’ for 10^8 integers. However, the Niven numbers in the second, third, etc. million can be found equally quickly by adding 1, 2, etc. (or their digit sums) to the digit sums found for the first million. In this way the Niven numbers less than 10^12 can be investigated. There are in fact 27975 Niven numbers in the millionth group of millions of integers, the largest being 999999999903. (I can’t tell you which position it occupies in the complete Niven sequence.)

In the following realisation, the J verb, niv, may be used monadically to produce the digit sums for 10^y integers (including zero) and then dyadically to find the Niven numbers among the x*10^(y) to (x+1)*10^y-1 integers, where x and y are respectively left and right arguments of the verb. If y is set to 6, the integers are explored in groups of one million. If ‘n’ successive millions are analysed by one J statement, the verb reports, for each successive group, the total number of integers examined up to that point, the number of Nivens in the group, the Nivens in the group (recorded for later interrogation in a vector FN but overwritten by the Nivens in the next group, if there is one), and the total number of (overwritten) Nivens in the previous groups, this last being given to enable an ‘N’ to be associated with each finally recorded ‘FN’. The example provided shows the analysis of 10 successive groups each of 10^6 integers; analysis time is proportional to the number of groups and this analysis took 30 seconds. (If a smaller group size is used, e.g. 10^5 integers, the time per group falls so that there is very little difference in the overall time to examine the same total number of integers — but the number of Nivens stored for interrogation falls.)

[In another article, Vector Vol.14 No.3, pp 138–142, De Kerf looks at Armstrong numbers. The above approach can be adapted to study this domain. The analysis is quite straightforward as far as the first group of integers is concerned, but beyond that matters become slightly more complex. For example, if the sums of 8th powers of the digits of the six-figure integers up to 10^6 were found, they could only be used as a basis for finding the Armstrong numbers in the 10th to the 99th million groups, i.e. for the addition of two and only two digits.]

a=. i.10   [   n=: 0
int=. <. = ]              NB. verb: integer test ( yields 0 or 1 )
sumt=. +/                 NB. verb: Sum table
f=. ,@sumt&a              NB. verb: Ravelled table of sum of a and ?
niv=. 3 : 0
y=. <: y.                 NB. y is y. minus 1
#k=: i.#s=: f^:y a        NB. Repeated application of f on a
:
S=. s+x.{s                NB. Add x.th s to each s
K=. k+x.*#k               NB. Add x. tallies of s to each k
FN=: K#~int K%S           NB. Niven numbers in the x.th group
D=: n                     NB. D is total No. of Nivens overwritten
n=: n+#FN
z=: (_1{K),D,(#,_1&{)FN   NB. 4-vector:
                          NB.  (1)Total No. of integers exam'd, (2) D,
                          NB.  (3,4) No. of Nivens and largest in final group
)

   0!:0<'c:\j305c\temp\niven.js'
   niv 6
1000000
   (i.10)niv"0 0 y=.6

           -----------------Niven Numbers----------------
Integers
Examined      Overwritten       In this group        Largest
 999999                 0               95428         999990
1999999             95428               91133        1999998
2999999            186561               87403        2999970
3999999            273964               83959        3999996
4999999            357923               80872        4999968
5999999            438795               78193        5999994
6999999            516988               75678        6999966
7999999            592666               73361        7999992
8999999            666027               71069        8999984
9999999            737096               68999        9999990

E.A.Clough