Problems & Puzzles: Puzzles

Puzzle 207.  The inventory sequences and the self-inventoried numbers

For sure you know the popular look and say infinite sequence (A005150):

1, 11, 21, 1211, 111221, 312211, 13112221, 1113213211, 31131211131221, 13211311123113112211, 11131221133112132113212221, 3113112221232112111312211312113211, ...

Let's take a closer examination of the way of calculating each member of the sequence.

For example from 1211 you look the first group of 1's and say '11'; then you see the next group of 2's and say "12"; finally you see the last group of 1's and say "'21', giving the whole next member of the sequence 111221.

But what if instead of taking partial views of the digits of 1211 you take exhaustive views of all the digits, as encountered, and say the total of each? In doing so, the next member to 1211 would be 3112 instead of 111221.

Proceeding this way from a starting number "1" this is what is obtained (A063850)

1, 11, 21, 1211, 3112, 132112, 311322, 232122, 421311, 14123113, 41141223, 24312213, 32142321, 23322114, 32232114.

Now the sequence 'ends' in a cycle of 'period 2' because from 23322114 follows 32232114 but from 32232114 follows 23322114.

Up to here we are just reviewing well known facts about two well known sequences.

A. Now here comes a challenging assertion from Clifford A. Pickover. He says (*) that this last kind of sequences were studied by certain Roger Hargrave from West Sussex, U.K. and that:

"oddly, he [Hargrave] believes that all his sequences [starting in any number?] finally oscillate between 23322114, 32232114. Can you prove this?"

Maybe a better phrase would have been "can you prove or disapprove this"? Because the  real fact is that the Hargrave's statement is easily disapproved.

Just a couple of examples:

1) If the starting number is 22, the sequences 'ends' immediately in a cycle of period 1.

2) If the starting number is 40, the sequence 'ends' in a cycle of period 4:

40, 1410, 211410, 12311410, 4112131410, 2451121310, 221415411310, 225124151310, 322541141310, 232215244110, 421331152410, 242241231510, 422431131510, 242223411510, 422413311510

BTW, Hargrave named these sequences Gleichniszahleninventar, name that I like it because of the "inventory-action" idea reflected in the name.

Following this idea I will call these sequences as "inventory sequences" and "self-inventoried numbers" to such starting numbers that immediately end in a cycle of period 1, as the number 22 does.

B. Other than 22, are there more self-inventoried composite numbers?

Yes; they are a lot of them. Here are the first 10 of them:

 Self-inventoried composites, by C: Rivera, January, 2003 22, 33311012, 33311014, 33311015, 33311016, 33311018, 33311019, 33311210, 33311214, 33311215, ...

C. Are there self-inventoried primes?

Yes, but they are sparser than the self-inventoried composites. Here are the first 10 of them that I have gotten by an exhaustive search below 2^32:

 Self-inventoried primes, by C: Rivera, January, 2003 33311017, 33311417, 33311519, 2233311419, 2233311617, 3322311017, 3322311617, 3331102219, 3331192217, 3331221917, more?

D. Now, let's see the inventory sequence starting with the prime 7:

7, 17, 1117, 3117, 132117, 31131217, 23411217, 2213143117, 2241231417, 3224311317, 3322143117, 3322311417, 3322311417

In this case we notice that a) there are 3 consecutive primes (7, 17 & 1117) b) the sequence ends in a cycle of period 1 with a self-inventoried composite number (3322311417)

Here is a list of the starting prime number that generates a sequence of K primes in its  corresponding inventory sequence:

 K Inventory sequence of K primes (1 to 7 by CR) 1 2 2 3, 13 3 7, 17, 1117 4 11173, 311713, 233117, 12232117 5 29527, 22191517, 2231191517, 221341191517, 22511314191517 6 8986717, 2819162711, 221841191617, 22511814191617, 2215611814191617 2271152618141917 7 2222228557 62182517 162221181517 511632181517 25511613121817 22256116131817 32152651131817 8 See below a solution by Jon Wharf. Is this the least solution?

And our questions are:

1. Do all the inventory sequences end in a cycle, or is there a starting number generating an endless inventory sequence?
2. Is there a finite number of cycles at the end of the inventory sequences? If so, what is the cycle with the largest period?
3. Can you find a starting prime number that generates more than 7 consecutive primes in its corresponding inventory sequence?
4. Are there infinite self-inventoried composite numbers? If not, can you find the largest one of these?
5. Are there infinite self-inventoried prime numbers? If not, can you find the largest one of these?
6. Can you extend the list of the self-inventoried primes given above?
7. Can you find a starting number that, in its own inventory sequence, generates an ending cycle composed only of prime numbers?

__________

(*) See p. 321, "Wonders of Numbers", Oxford 2001

Solution: Joseph L. Pe and Jon Wharf sent excellent answers for this puzzle. Jon Wharf brings as a follow up of his search new specific challenges to question 3, 4 & 5.

Joseph L. Pe wrote:

ANSWER TO Q1. Any inventory sequence ends in a cycle.

Proof. Let D(n) denote the number of digits in the decimal expansion of n, and let g denote the inventory sequence generator function (for example, g(1211) = 3112). Then the inventory sequence beginning with N, denoted IS(N), can be written as: N, g(N), g(g(N)),.... Note that if any two terms of IS(N) are equal, then IS(N) ends in a cycle.

I. If the digit d = 0, 1, ..., 9 appears exactly once in n, then d contributes two digits to g(n), hence d increases the number of digits by 1 in going from n to g(n). (For example, g(5) = 15 and g(12) = 1112.) If d appears exactly twice in n, then the corresponding increase is 0. (For example, g(33) = 23). But if d appears exactly k > 2 times in n, then d decreases the number of digits by k-D(k)-1 > 1. (For example, g(2222) = 42 where k = 4 and the net decrease is 4-1-1 = 2 digits; and g(1111111111) = 101 where k = 10 and the net decrease is 10-2-1=7 digits.)

II. Lemma. If D(n) <= 20, then D(g(n)) <= 20.

For suppose that n has at most 20 digits. The digits of n can be partitioned into two finite sequences: S, consisting of the first occurrences of digits of n, and S', consisting of the other occurrences of the digits. (For example, if n = 11133245, then S = {1,3,2,4,5} and S' = {1,1,3}.) By I above, each member of S increases the number of digits by 1 in going from n to g(n), whereas each member of S' either cancels a potential increase of 1 (when the digit occurs exactly twice in n) or decreases the number by at least 1 (when the digit occurs more than twice in n). But S has at most 10 members, so there are at most 10 increases in the number of digits from n to g(n). Hence, in the case that 1 <= D(n) <= 10, clearly D(g(n)) <= 20. In the case that 11 <= D(n) <= 20, then S' has at least D(n) - 10 elements, and the net increase can be at most 10 - (D(n) - 10) = 20 - D(n), so that, D(g(n)) <= D(n) + (20 - D(n)) = 20. In any case, if D(n) <= 20, then D(g(n)) <= 20.

III. Lemma. If D(n) > 20, then g(n) < n.

For using the notation of II above, S can have at most 10 terms, whereas S' must have at least 11 terms, one of which must decrease the number of digits going from n to g(n) (since there can be no more than 10 of the digits that occur exactly twice). That is, S has fewer terms than S'. Hence, g(n) will have fewer digits than n, implying g(n) < n.

IV. By repeatedly applying III above, if necessary, one obtains a term M of IS(N) such that M <= 10^20 (that is, D(M) <= 20). By II, all terms of IS(N) from M onwards are <= 10^20. Since these infinitely many terms can take only 10^20 possible values, at least two of them must be equal. Therefore, as noted above, IS(N) must end in a cycle. Note: 10^20 is probably the sharpest upper bound for cycle terms. For example, if

N = 12345678901234543212456778605948376273848494934857594839304384/ 000000009303030, then IS(n) ends in the cycle 24228118271513161910, 42142871171513161910, 24228118271513161910, .... which are 20-digit numbers.

I. There are only a finite number of cycles at the end of inventory sequences.

Proof. Since all but finitely many terms of IS(N) are <= 10^20, all the terms of a cycle must be <= 10^20. But each cycle is just a finite sequence of integers which are all distinct. Hence, the number of possible cycles <= the number of permutations of the set {1, 2, ..., 10^20} = (10^20)!, which is a finite number.

II. Of course, this is an absurdly large upper bound. Probably the largest period is 4, first attained at N = 40: 40, 1410, 211410, 12311410, 4112131410, 2451121310, 221415411310, 225124151310, 322541141310, 232215244110, 421331152410, 242241231510, 422431131510, 242223411510, 422413311510, 242241231510, .... I have checked that no number < 10^6 has a greater period.

In principle, it would be simple to prove that no inventory sequence has a cycle length > 4. By the previous proof, any cycle begins with a number <= 10^20. Hence, the claim would be proved by just checking that IS(N) has cycle length <= 4, for all N <= 10^20. I leave the verification up to someone with sufficient computing resources.

Q4 and Q5: There can be only finitely many self-inventoried numbers (hence, only finitely many self-inventoried prime numbers and composite numbers.) This is because, by the lemma III I proved below, any n > 10^20 must have g(n) > n; so if n is self-inventoried, then we must have n <= 10^20 [This is slightly incorrect, see Jon Wharf's solution to the question Q4.]

***

Jon Wharf wrote:

I've looked at that first 5 questions and the short version is:

1) all the inventory sequences end in a cycle
2) there is a finite number of cycles, largest period appears to be 4 (not
definite)
3) 222222222222222222222288577755557777777777777777777 (which is probably
prime) leads to seven more primes, eight in all
4) Finite selfinv composites; my largest is 221111918171615141310.
5) Finite selfinv primes; my largest is 1111918171614101513.

...

Define the inventory function inv(n) as the inventory number generator.

An inventory number is one that can be generated as an inventory for another number (a result of inv(n)). Almost all numbers are inventory numbers; the requirements are:

a) at least two digits and the last digit not zero -> inventory

b) at least four digits, ends in zero, and contains two consecutive non-zero digits excluding the leading digit -> inventory

c) the number ten -> inventory (inv(0))

Otherwise it is not an inventory number, eg 10000, 120304050. Interestingly this means all primes > 10 are inventory numbers.

Define a stable inventory number m as an inventory number whose own inventory number inv(m) has at least as many digits as m. Clearly any terminal cycle sequence must include a stable inventory number (at least every other term, in fact).

Now an inventory number consists of at most ten q-d sets, where q is quantity and d is digit. Sum of q<i> is the number of digits in the original number. In order for an inventory number k to have 100 digits it must inventorise a number of at least 10^9 (=10*10^8) digits, and inv(k) will have at most 30 digits (=(2+1)*10), inv(inv(k)) will have at most 22 digits (=3+3+2*8), and inv(inv(inv(k))) can only have at most 21 digits. So it is clear that a stable inventory number has 21 or less digits. It's also clear that any 21-digit number will inventorise to 21 or less digits, so this is a one-way limit - no inventories 21 digits or less will produce inventories over 21 digits. Also, a sequence starting in non-stable numbers will quickly move to include stable numbers.

This gives us directly that (Q1) the number of stable inventory numbers is finite and so there are no endless inventory sequences, (Q2) there are a finite number of end cycles, and (Q4 & 5) there are only finite self-inventoried composites and primes.

(Q2) Looking at the ending cycle of any sequence, it must have a constant number of q-d sets, since once a particular d occurs it never leaves. Some of these will be "active" and some "passive" - "active" meaning that the q changes for this d in the cycle and "passive" meaning it never does. All active q-d sets occur before any passive q-d set, in the end cycle. There is obviously an opportunity to reorder the passive sets at the end to produce primes.

For stable 21 digits, one q<i> must be 10 or more, so there will be at least 7 q<i> == 1. So it must be q<1> >= 10. The largest other possible q value would be 3 (10+3+8*1=21). The possibilities for non-unit q are {10,3}, {10,2,2}, {11,2} and {12}. {10,3} -> {10,2,2} is non-stable -> 20 digits -> {8,2,2,2}. {12} -> {11,2} becomes selfinventorising.

For 20 digits, there are more possibilities for non-unit q: {11}, {10,2}*, {9,3}*, {9,2,2}*, {8,4}*, {8,3,2}*, {8,2,2,2}*, {7,5}*, {7,4,2}*, {7,3,3}*, {7,3,2,2}#, {7,2,2,2,2}*, {6,6}*, {6,5,2}*, {6,4,3}*, {6,4,2,2}#, {6,3,3,2}#, {6,3,2,2,2}#, {6,2,2,2,2,2}*, {5,5,3}*, {5,5,2,2}*, {5,4,3,2}*, {5,4,2,2,2}#, {5,3,3,3}*, {5,3,3,2,2}#, {5,3,2,2,2,2}*, {5,2,2,2,2,2,2}*, {4,4,4,2}*, {4,4,3,3}*, {4,4,3,2,2}#, {4,4,2,2,2,2}*, {4,3,3,3,2}#, {4,3,3,2,2,2}*, {4,3,2,2,2,2,2}#, {4,2,2,2,2,2,2,2}#, {3,3,3,3,3}*, {3,3,3,3,2,2}*, {3,3,3,2,2,2,2}*, {3,3,2,2,2,2,2,2}*, {3,2,2,2,2,2,2,2,2}* and {2,2,2,2,2,2,2,2,2,2}. ({7,4,2} and {8,2,2,2}) form a 2-cycle reached by all *, {7,3,2,2} self 2-cycles, reached by all #, and both {11} and {all 2} get to 21 digits and {11,2}. None are self-inventorised.

For 19 digits, only the set missing 2, {11}\2 is stable, and self-inventorises.

18 digits strongly resembles 20 digits, with end 2-cycles

({6,4,2},{7,2,2,2}) and ({6,3,2,2})

17 and lower odd numbers of digits cannot give end-cycles.

And so on. Once the number of ones starts to interact with the number of twos or threes we stand some chance of more interesting behavior, but I haven't yet found an end-cycle of more than 4.

(Q3) No doubt there is a prime which inventorises to 2222228557 or one of the similar primes, eg 2222855227 (22:2, 2:8, 5:5, 22:7, should be plenty there and "only" 51 digits). 222222222222222222222288577755557777777777777777777 seems to work. (thanks to Joe Crump's ZZMath Excel addin)

(Q4) The largest (21-digit) self-inventoried number I've thought of is 221111918171615141310. This and all scrambling are divisible by 3. Eleven ones, two twos and one of each other digit is the only possible self-inventoried solution set for 21 digits so primes will be smaller.

(Q5) There are no 20 digit self-inventoried numbers so we drop to the {11}\2 solution for 19 digits and 1111918171614101513 is my candidate for largest self-inventoried prime.

***

And the added challenges by J. Wharf are: can you improve his findings for the questions 3, 4 & 5 (numbers in bold-red)?

***

Reviewing (Feb. 2004) the Warf's candidate for the largest self-inventoried prime I (C. Rivera) found that he was too close to find the real largest one: 1111918171614121013 !!!

*** Records   |  Conjectures  |  Problems  |  Puzzles  Home | Melancholia | Problems & Puzzles | References | News | Personal Page | Puzzlers | Search | Bulletin Board | Chat | Random Link Copyright © 1999-2012 primepuzzles.net. All rights reserved.