 |
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