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 = 5220; 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