Current issue

Vol.26 No.4

Vol.26 No.4

Volumes

© 1984-2017
British APL Association
All rights reserved.

Archive articles posted online on request: ask the archivist.

archive/22/1

Volume 22, No.1

At Play With J: Belgian Numbers

Eugene McDonnell

Belgian numbers were recently introduced by Eric Angelini. For N to be a Belgian number, it is necessary that it appear in the sum scan of lots of replications of N’s digits. For example, try the digits of 16:

   +/\8 $ 1 6
1 7 8 14 15 21 22 28  

So 16 isn’t Belgian. What about 17?

   +/\8$ 1 7
1 8 9 16 17 24 25 32  

So 17 is Belgian.

My first concern on hearing of them was to find out how one could tell whether a number was Belgian or not. Assume that N is 176; how many copies of 1 7 6 would be needed to reach 176 or thereabouts? This can be found by taking the ceiling of N divided by the sum of its digits S. Like this:

     N =: 176
     ] D =: 10&#.^:_1 N
     1 7 6
   ] S =: + / D
14
   ] C =: >. N % S
13  

Then multiplying this by its number of digits, in this case, 3, and sum scanning:

   ] R =: + / \  (C * 3) $ 1 7 6
1 8 14 15 22 28 29 36 42 43 50 56 57 64 70 71 78 84 85 92 98 99 106 112
113 120 126 127 134 140 141 148 154 155 162 168 169 176 182  

and, sure enough, we find that 176 is a Belgian number. This was, for the moment, an easy way to determine which numbers were Belgian – if they were not too big. I thought it might be possible to use it for numbers up to about ten million – but thereafter it gets ridiculous. For example, suppose that one wants to see whether 1234567898765 is Belgian:

   N =: 1234567898765x
   ] D =: 10 &. #. ^_1 N
   #D
13
   ] N=:+/D
71
   >. B % S
17388280265
   13 * >. B % S
226047643445  

Ouch. A fifth or so of a trillion (US style) digits. I concluded that this was impractical.

There had to be a better way. Eventually I thought I saw that in the case of 176 there was a threeness lurking. I decided to form them into a table of three-item rows, together with the first difference of the rows, and the 14-residues of the whole table:

   qn =: 13 3 $ + / \ 39 $ 1 7 6
   qn      ;(2-~/\qn);14|qn
+-----------+--------+-----+
|  1   8  14|14 14 14|1 8 0|
| 15  22  28|14 14 14|1 8 0|
| 29  36  42|14 14 14|1 8 0|
| 43  50  56|14 14 14|1 8 0|
| 57  64  70|14 14 14|1 8 0|
| 71  78  84|14 14 14|1 8 0|
| 85  92  98|14 14 14|1 8 0|
| 99 106 112|14 14 14|1 8 0|
|113 120 126|14 14 14|1 8 0|
|127 134 140|14 14 14|1 8 0|
|141 148 154|14 14 14|1 8 0|
|155 162 168|14 14 14|1 8 0|
|169 176 182|        |1 8 0|
+-----------+--------+-----+  

The first row of the first table shows that the sum of the integers is 14; the second table shows that each row differs from the previous row by 14, the third table shows that the 14-residue of each row is 1 8 0.

The point made by the second table is that each row after the first is formed by adding 14 to the preceding row. This means that I could create qn exactly by adding multiples of 14 to the starting row:

   (14 * i. 13) + / 1 8 14
  1   8  14
 15  22  28
 29  36  42
 43  50  56
 57  64  70
 71  78  84
 85  92  98
 99 106 112
113 120 126
127 134 140
141 148 154
155 162 168
169 176 182

The point made by the third table is that any concern about residues after the first row is irrelevant.

With this information at hand, we’re almost there. The number 176 is 8 beyond 168, which is 14 * 12. The 14 * 12 is irrelevant; the 8 is significant. It means that 8, which is 14|176, is of great importance. It is one of the numbers in the first row of the table, and after being added to by multiple 14s, must arrive at 176, and so, is Belgian! This is a perfectly general observation, and allows any integer to be tested for Belgianity. Here is an outline of the steps to take to see if N is Belgian:

Let D be the digits of N.

Let S be the sum-scan of the digits of N.

Let T be the sum of D (which is also the last item of S).

Let R be the T-residue of N.

Then N is Belgian if R is in S.

For the case of N = 176, we have:

D is 1 7 6

S is 1 8 14

T is 14

R is the T residue of N, or 8.

We ask: is R in S? The answer is Yes!

The general case is that N is Belgian if:

(M | N) e. S

is 1.

Now it’s clear that 176 is Belgian if any of these residues is the same as 14 | 176:

   14| 176
8

It is certain that if one adds the proper multiple of 14 to 8, the result must be 176. It isn’t necessary to find what this multiple is. It is sufficient that there is an 8 in the sum scan of 1 7 6.

Now we can write an expression to let us determine whether 176 is Belgian:

   (14 | 176) e. + / \ 1 7 6
1  

Another way of doing this is: since 8 is the 14 residue of 176, it is sufficient to see whether there is a zero in the 14 residue of 176 - + / \ 1 7 6

   14 | 176 - 1 8 14
7 0 8  

So we may write:

   0 e. 14 | 176 - + / \ 1 7 6
1  

to determine that 176 is Belgian.

We can now work with large numbers with some confidence. First, we’ll need a way of getting the integer components of N. The function dig works very well:

   dig =: 1j1 & # &. ": @ x:

We’ll use this on 1234567898765:

   dig 1234567898765
1 2 3 4 5 6 7 8 9 8 7 6 5
   + / \ dig 1234567898765
1 3 6 10 15 21 28 36 45 53 60 66 71
   +/1 2 3 4 5 6 7 8 9 8 7 6 5
71
   71 | 1234567898765 - + / \ dig 1234567898765
20 18 15 11 6 0 64 56 47 39 32 26 21  

There is a zero in this list, indicating that N is Belgian. We can verify this.

   N =: 1234567898765x
   S =: + / \ dig N
   M =: {: s
   S
1 3 6 10 15 21 28 36 45 53 60 66 71
   M
71
   Q =: <. N % M
   Q
17388280264
   P =: Q * M
   P
1234567898744
   R =: S + P
   R
1234567898745 1234567898747  1234567898750 1234567898754
1234567898759 1234567898765 1234567898772 1234567898780
1234567898789 1234567898797  1234567898804 1234567898810 
1234567898815
   N e. R
1  

So 1234567898765 is Belgian.

Here is a function that will determine whether or not a number is Belgian:

   BN =: 3 : 0 " 0
   N =. x: ^: (y. >: 2147483648) y.
   'S M' =. (] ; {:) + / \ (1j1 & # &. ":) N
   (M | N) e. S
   )  

The first line makes the argument an extended integer N if it is larger than the largest positive 32-bit integer, and otherwise leaves it alone. M and S are modulus and digits sum, as discussed above. See if BN agrees that N is Belgian:

   BN 1234567898765
1

Why Belgian?

Why Belgian, indeed. Well, there are Roman numbers, Arabic numbers, even Catalan numbers. It’s about time Belgium was recognized. I could pretend that Eric Angelini (the creator of these numbers) knew that my wife Jeanne was a Fulbright Scholar at the University of Brussels for the 1952-1953 year – and named them Belgian in her honour. But I have to admit that this is quite far-fetched. The truth undoubtedly is – because Angelini is Belgian.

1 Dec 2006


script began 3:18:46
caching off
debug mode off
cache time 3600 sec
indmtime not found in cache
cached index is fresh
recompiling index.xml
index compiled in 0.2727 secs
read index
read issues/index.xml
identified 26 volumes, 101 issues
array (
  'id' => '10005780',
)
regenerated static HTML
article source is 'HTML'
source file encoding is 'ASCII'
read as 'Windows-1252'
completed in 0.2997 secs