 Mari Numbers Mike Keith

### Introduction

Consider the integer 1266. Let the digits of this number be the initial terms of an integer sequence (d1=1, d2=2, d3=6, d4=6) and compute succeeding terms of the sequence via the recurrence

dn= dn-4+dn-3dn-2+dn-1

which yields the sequence

1, 2, 6, 6, 19, 57, 177, 1266, ...

in which the starting number (1266) appears. An integer like this, which appears in the sequence generated by its own digits, we call a Mari number. (MARI is an acronym for "Multiply-Add Recurrence Invariant".)

In general, we take an integer N with m digits (say d1d2d3...dm) and let d1, d2, d3, ..., dm be the initial terms of the sequence. The recurrence can be any formula of the form

dn= dn-mdn-m+1...dn-m+p1 + dn-m+t1+1dn-m+t1+2...dn-m+p2 + ... + dn-m+tr-1+1dn-m+tr-1+2...dn-m+pr

where p0 = 0 < p1 < p2 < ... < pr . Let ti = pi - pi-1 + 1 be the number of terms in the ith product in the recurrence; then we refer to a Mari number with those parameters as being a (t1 t2 t3 ... tr)-Mari number, or a Mari number of type (t1 t2 t3 ... tr). For example, since the recurrence in the example above, dn-4+dn-3dn-2+dn-1, has products with 1, 2, and 1 terms, this means 1266 is a (1,2,1)-Mari number.

Mari numbers are a generalization of both Keith numbers (which have been studied quite a bit since I introduced them in 1987) and Borris numbers (which were first defined in 1998). Keith numbers are Mari numbers of type (1,1,1...1) - i.e., the recurrence relation has no products, just a sum. Borris numbers are Mari numbers of type (m-1, 1).

For numbers with m digits, how many different types are there? The recurrence formula involved can be constructed by starting with the string

dn-mdn-m+1...dn-1

and inserting any number of + signs (from 0 to m-1) between elements of the string. Since each of the m-1 positions can either have or not have a + sign, there are 2m-1 ways to do this, and so there are 2m-1 Mari types for a given m.

### Some Results

Here is the complete list of Mari numbers up to 108:

```14 19 28 47 61 75

191 197 205 242 302 515 742

1064 1104 1220 1266 1537 1757 1981 2208 2580 3505 3684
4484 4608 4788 6702 7385 7647 7909 8180

13614 14327 15557 22251 24377 29662 31331 34285 34348
35577 39323 41180 50679 55604 59445 62662 75232 80005
86935 89043 93993 97915 99543 107894

120284 123270 128005 128136 129106 132065 145479 147640
156146 164841 166623 174680 182687 183186 194976 196836
207322 259208 272829 298320 327155 355419 378205 393544
398192 419904 434802 498486 525609 614605 633814 636824
694280 704106 925993

1076825 1084051 1110459 1190703 1261121 1277374 1441204
1545283 1656629 1690619 1861618 1945417 2012500 2068287
2069047 2072522 2237120 2615936 2705109 2785693 3311881
3426544 3458007 3883808 3919332 4041328 4155642 4417152
4665600 4849887 4856055 5076751 5242880 5308416 5746270
5766084 7193634 7586884 7605002 7913837 7986843 8560336
8575000 9891125

10101066 10493499 10642405 11436171 12023595 12140467 12743657
12761559 14571519 15120436 15871777 16564522 17809329 18407175
19075418 20448164 20631281 21595500 22505541 22541614 22898593
22902641 23022925 23721147 25600040 26756753 29423520 29724784
30314002 31464941 31593249 33252489 33445755 35269499 35415411
37071960 37691636 39301359 44121607 45162165 45794245 49013804
51076391 52428802 53889347 54906783 58178895 70645071 74076134
76085894 78470549 80427967 81411662 83538039 89970040 90115466
90486440 90699264 ```

In the above listing that we do not specify which Mari type each number is, but that information can be found in the listing at the end of the article, which groups them by type instead of sorting them by number.

The number printed in bold is, seemingly, very remarkable: it is the smallest, and so far the only known Mari number of two different types. 5242880 is a (3,4)-Mari number, because under that generating rule it produces the sequence

5 2 4 2 8 8 0 40 16 64 128 5242880

while at the same time it is a (4,3)-Mari number, with sequence

5 2 4 2 8 8 0 80 128 512 5242880

Note that 5242800 = 5·220; does this have anything to do with explaining this phenomenon? Are there other multiple-Mari numbers like this?

The number of Mari numbers with m digits (for m=2, 3, ...) is

6, 7, 19, 23, 36, 44, 58, ...

for a total of 193 up to 108.

Table 1 at the end of this article shows the Mari numbers for each m grouped by type. We see that, for every m, not all of the 2m-1 possible types actually occur. The number of types which admit Mari numbers for m=2, 3, ... are:

1, 3, 5, 12, 20, 32, 42, ...

(instead of 2, 4, 8, 16, 32, 64, 128...). These values divided by 2m-1 are

0.5, 0.75, 0.625, 0.75, 0.625, 0.5, 0.328...

What can be said about the limit of this sequence? Is it, perhaps, zero?

Is it possible to prove that certain types cannot admit Mari numbers? The most tantalizing case is type (m), in which the recurrence relation is just the product of the m previous terms. Although it seems certain that there are no Mari numbers of type (m), as far as I know there is no proof. However, we do have the following theorem:

Theorem: There are no Mari numbers of type (m) less than 10100.

Proof: First, we have the

Lemma: For N to be a Mari number of type (m), it is necessary (not sufficient) that:

(a) N has no zero digits, and

(b) if P is the set of prime numbers that divide evenly into at least one of the digits of N, and Q is the set of primes that divide evenly into N, then P=Q.

Part (a) is necessary becuase otherwise all terms of the sequence after the first m terms will be zero. For part (b), we see that P cannot contain any primes not in Q since then it will be impossible to produce N by multiplying together the elements of Q. On the other hand, Q cannot have any primes not in P, since all the factors in Q will be present in every term of the sequence. Thus, P=Q.

(Thanks to e-mails from Keith Ramsay, Kurt Foster, and Iain Davidson for this lemma.)

A corollary of this lemma is that N must be of the form 2a3b5c7d. Also, an N that satisfies (a) and (b) is not necessarily an (m)-Mari number, but what is true is that kN will appear eventually in the sequence, for some k (not necessarily 1, which is what is needed to make it a Mari number).

Finally, we examined all integers of the form 2a3b5c7d less than 10100 by computer, determined which satisfy (a) and (b), and computed their Mari sequence until we found kN. In no case was k=1 found, which proves the theorem.

Note that there are a few near-misses with small values of k; the "best" ones are 128, 384, and 2333772, which have k=2, 8, and 6, respectively:

128: 1, 2, 8, 16, 256 (= 2 x 128)
384: 3, 8, 4, 96, 3072 (= 8 x 384)
2333772: 2, 3, 3, 3, 7, 7, 2, 5292, 14002632 (= 6 x 2333772)

In fact, the largest integer that satisfies both (a) and (b) less than 10100 is the 16-digit 2877833474998272. Heuristic arguments suggest that there are no more such integers beyond 10100, which leads to two conjectures:

Conjecture 1: There are no Mari numbers of type (m).

Conjecture 2: 128 is the only integer N that generates 2N in its (m)-Mari multiplicative sequence.

More generally, it seems that types whose last digit in the type specifier is "large" tend to not yield any Mari numbers. Can this be made more precise?

Table 1
All Mari Numbers up to 108.

```Type    Mari Numbers
11	14 19 28 47 61 75

12	191 242 515
21	205 302
111	197 742

22	4608
31	1220 1757 3505 4484
121	1266 8180
211	1064 1981 6702
1111	1104 1537 2208 2580 3684 4788 7385 7647 7909

23	13614
41	59445 80005 99543
113	97915
122	75232
212	15557 35577
131	50679
221	22251
311	41180
1112	24377
1211	29662 89043
2111	14327 39323
11111	31331 34285 34348 55604 62662 86935 93993

15	259208
33	128136
42	419904
51	393544
114	614605
213	128005 525609
132	166623
141	145479
231	123270
321	207322 378205
1122	398192
1221	107894 194976 704106
2121	327155
1311	182687
2211	498486
11112	636824
11211	132065 196836
12111	272829
21111	164841 434802 633814
111111	120284 129106 147640 156146 174680 183186 298320 355419 694280 925993

25	1261121
34	4665600 5242880 5308416
43	3426544 5242880
61	1545283
115	1441204 7605002
214	1190703 3919332
223	2237120
313	1277374
322	8575000
412	4856055
151	2072522 2705109 3311881 7986843
241	4155642
421	5076751
2113	3458007
1141	2615936
1231	4849887
1321	7193634
2221	5766084 9891125
2311	4417152 5746270
3211	2785693 3883808 7586884
11212	1861618
11221	1110459
12121	2068287
11311	1690619
12211	4041328
21211	2012500
31111	2069047
111112	1076825
111121	1656629
111211	1945417
121111	8560336
1111111	1084051 7913837

17	52428802
26	90699264
71	31593249 33252489
116	12761559 15120436
215	58178895
323	12023595
152	20448164
161	12743657 83538039 90486440
251	10101066 25600040
341	29724784 53889347
1115	54906783
2132	78470549
2321	49013804 76085894
3311	80427967
11222	29423520
22112	14571519 22902641 39301359
31112	23721147 51076391
12131	31464941
11321	89970040
13121	10493499
12311	15871777
13211	90115466
22211	23022925
31211	16564522
14111	20631281 45794245
23111	19075418
32111	30314002
41111	74076134
112112	22898593 35415411
111221	22505541 35269499
112121	81411662
121121	21595500
111311	17809329
112211	18407175 22541614
121211	37071960
113111	45162165
212111	10642405
221111	70645071
1112111	12140467
1121111	26756753
2111111	37691636
11111111	11436171 33445755 44121607 ```