Melissa's Numbers

Question

Melissa has noticed that certain positive integers can be written as the product of other integers, none of which uses any of the digits in the number itself, 512, for example (512 = 4 x 4 x 8).

Ten consecutive positive integers cannot all be one of Melissa's numbers. What about nine? And if not, what is the longest sequence of consecutive numbers all of which are Melissa's numbers?

I'm currently working on finding the longest sequence of Melissa's numbers for numbers up to 100, and have a question for 70: Can I write it as 70=235, or do I have to write it as 70=27*5 and therefore 70 is not a Melissa number? — CrSb0001, Mar 13 '24 at 16:37
Side note: it took me a little bit to determine that there were infinitely many Melissa's numbers—note the pattern $12=3\times4$, $102=3\times34$, $1002=3\times334$, $10002=3\times3334$.... — Greg Martin, Mar 16 '24 at 19:40
@GregMartin It also took me a while to realize that there are infinitely many pairs of consecutive numbers both of which are Melissa's numbers: (9,10), (99 x 100), (999, 1000), etc. Are there infinitely many triples? Don't know! Pity 101, 1001, 10001... is often prime. — Bernardo Recamán Santos, Mar 17 '24 at 02:07
Great puzzle! I've spent way too much time on this without making much progress... — Dmitry Kamenetsky, Mar 20 '24 at 06:15
Is there a Melissa number that requires 4 or more factors to be constructed? — Dmitry Kamenetsky, Mar 20 '24 at 13:23
@DmitryKamenetsky The Melissa number $16384$ can only be done with exactly $14$ factors. — , Mar 20 '24 at 18:37
@BernardoRecamánSantos I have updated my answer. I believe there are infinitely many quadruples of consecutive Melissa numbers :) — Dmitry Kamenetsky, Mar 21 '24 at 14:36
has the sequence of Melissa numbers been added to https://oeis.org ? — kuantumleap123, Mar 26 '24 at 09:02

score 18 · Answer 1 · 2024-03-15T18:28:55.047

The observations below narrow down the search space for a sequence of nine consecutive Melissa numbers quite a bit. The first number in the sequence ends in either $06$, $16$, $26$, $56$, $76$, $86$ or $96$. The rest of the number, which is the same for all numbers in the sequence, consists of at most five distinct digits, being $0$, $1$, $9$ and at most two other even digits. First some terminology:

For a Melissa number $n$, a Melissa factorization is a factorization $n=d_1\times\cdots\times d_k$, where the $d_i$ share no digits with $n$. We call each $d_i$ a Melissa factor of $n$.
For a Melissa number of $m$ digits, we call the last two digits its end and the first $m-2$ digits its start.

Observation 1: A Melissa number cannot end in $5$.

Proof. A number $n$ ends in $5$ if and only if it is an odd multiple of $5$. Then in any factorization, one of its factors is an odd multiple of $5$, and hence it ends in $5$. Then it shares a digit with $n$, and so $n$ is not a Melissa number.

This already shows that there is no sequence of ten or more consecutive Melissa numbers.

Observation 2: A sequence of five or more consecutive Melissa numbers cannot have a $5$ in their start, and cannot have a number ending in $50$.

Proof. As a consequence of observation 1, such a sequence contains a Melissa number ending in $0$, which is therefore divisible by $5$. Then one of its Melissa factors is divisible by $5$, and so it ends in $0$ or $5$. It cannot end in $0$, so one of its Melissa factors must end in $5$, and hence the start of the Melissa number cannot contain a $5$, nor can it end in $50$.

Observation 3: A sequence of eight or more consecutive Melissa numbers cannot have any odd digit other than $1$ or $9$ in their start, and cannot have a number ending in $40$ or $70$.

Proof. We already saw in observation $1$ that no such sequence contains a $5$ in their start. Such a sequence of length eight contains Melissa numbers ending in $3$ and $7$. Any Melissa factorization of a number ending in $3$ contains only odd factors, none of which end in $3$ or $5$. Products of factors ending in $1$ or $9$ also end in $1$ or $9$, and hence there must be a Melissa factor ending in $7$. It follows that the Melissa number does not contain any $7$, so none of the Melissa numbers contain a $7$ in their start, and in particular it does not end in $73$, so the sequence does not contain a number ending in $70$.

The same argument shows that any Melissa number ending in $7$ must have a Melissa factor ending in $3$, so none of the Melissa numbers contain a $3$ in their start, and in particular it does not end in $37$, so the sequence does not contain a number ending in $40$.

Observation 4: In a sequence of nine or more consecutive Melissa numbers, their start cannot contain three distinct even nonzero digits.

Proof. Such a sequence contains Melissa numbers ending in $2$, $4$, $6$ and $8$. Any Melissa factorization of a number ending in $2$ must have an even factor not ending in $0$. Then this factor must end in one of $\{4,6,8\}$, and so the start of the Melissa number cannot contain all three digits $\{4,6,8\}$. The same goes for the Melissa numbers ending and $4$, $6$ and $8$, and this concludes the proof.

As I understood,, if the first number in the sequence of consecutive numbers ends in 96 and the rest of the number is the same for all numbers in the sequence then the sequence consists of at most four numbers. — Alex Ravsky, Mar 15 '24 at 19:03
@AlexRavsky Frankly, I hadn't given any thought to the case where the 'start' of the numbers changes. In this case the next number will end in $d000\ldots00$ where $d$ is one greater than one of the original digits, which is either $1$ or even. So $d=2$ or $d$ is odd, and by the same observations $d\neq5$ and $d\neq7$. So $d\in{1,2,3,9}$. Not sure if we can say more. — , Mar 15 '24 at 20:37

isaacg · Answer 2 · 2024-03-15T01:52:28.573

13

Update: I extended my calculation to $10^9$. I didn't find any longer runs than before, but I found another run which matched my record:

Another length 7 run: 16161608-16161614
16161608 = 53 * 3244 * 94
16161609 = 57 * 283537
16161610 = 5 * 3232322
16161611 = 5389 * 2999
16161612 = 4 * 4040403
16161613 = 29 * 557297
16161614 = 2 * 8080807

Going much further will require something smarter than a brute force approach.

Repository: https://github.com/isaacg1/melissa/

I calculated the first runs of Melissa's Numbers of each length, for numbers up $10^7$. The longest run I found was

Length 7:
4
8-9
8-10
258-261
666-670
101176-101181
6777666-6777672

For the longest of these runs, we have the following factorizations:

6777666 = 14 * 484119
6777667 = 13 * 521359
6777668 = 2122 * 3194
6777669 = 123 * 55103
6777670 = 2 * 3388835
6777671 = 2099 * 3229
6777672 = 44 * 154038

edited Mar 15 '24 at 01:52

answered Mar 13 '24 at 17:07

isaacg

6,915
1
19
52

1

Makes me wonder if you'll also find a length-8 run below 10⁸ and a length-9 run below 10⁹. – Oliphaunt Mar 14 '24 at 09:12
2

The first thing coming to my mind is that you could download a list of prime numbers to generate candidate ranges. Unless you were already doing that. – Oliphaunt Mar 14 '24 at 09:20
5

@Oliphaunt Update: Searched to $10^9$, didn't even find a length-8 run. – isaacg Mar 14 '24 at 21:57
Would you mind sharing your code for this? I'm curious to see how you calculated it – DialFrost Mar 15 '24 at 00:28
2

@DialFrost Added the repository – isaacg Mar 15 '24 at 01:44
4

If there exists an 8+ run with a prefix consisting of only two digits, with the last two digits being arbitrary, it has to be > 10^14 – SE - stop firing the good guys Mar 15 '24 at 05:20

score 11 · Answer 3 · answered Mar 13 '24 at 15:52

11

Partial answer:

Every number that ends with 5 cannot be one of Melissa's numbers, because you will need to use 5 to write the number as a product, but 5 is already the last digit

Prime numbers are also not allowed, because they can only be written as $x = 1 * x$ which uses all the digits of the number.

answered Mar 13 '24 at 15:52

WOWOW

423
14

7

The prohibition on fives also means a run cannot be longer than nine, as their are nine numbers between every odd multiple of five, excluding both endpoints. This is how OP provided the upper bound of ten – No Name Mar 14 '24 at 04:56

Dmitry Kamenetsky · Answer 4 · 2024-03-22T01:53:50.670

I confirm @isaacg's results. I found some more sequences of length 6 that may be useful for spotting a pattern:

11116657 = 29 * 383333.
11116658 = 2 * 7 * 794047.
11116659 = 23 * 483333.
11116660 = 5 * 524 * 4243.
11116661 = 43 * 258527.
11116662 = 3 * 3705554.

11666666 = 22 * 530303.
11666667 = 3 * 3888889.
11666668 = 52 * 224359.
11666669 = 47 * 248227.
11666670 = 2355 * 4954.
11666671 = 29 * 402299.

64664456 = 2 * 32332228.
64664457 = 33 * 923 * 2123.
64664458 = 2 * 32332229.
64664459 = 173 * 373783.
64664460 = 27 * 28 * 85535.
64664461 = 29 * 2229809.

161116659 = 33 * 4882323.
161116660 = 5 * 32223332.
161116661 = 53 * 3039937.
161116662 = 3 * 53705554.
161116663 = 29 * 5555747.
161116664 = 2 * 80558332.

2221828216 = 4 * 555457054.
2221828217 = 49 * 45343433.
2221828218 = 3 * 740609406.
2221828219 = 73 * 30436003.
2221828220 = 5 * 444365644.
2221828221 = 3 * 740609407.

Also I believe there are infinitely many quadruples!

1909899 = 3 * 636633.
1909900 = 4 * 477475.
1909901 = 7 * 272843.
1909902 = 3 * 636634.

Now insert "09".
190909899 = 3 * 63636633.
190909900 = 4 * 47727475.
190909901 = 7 * 27272843.
190909902 = 3 * 63636634.

We can continue inserting "09" indefinitely. So we have 19(09)899 - 19(09)902 where (09) is repeated 1 or more times is always a quadruple of consecutive Melissa numbers.

number of Melissa numbers less than or equal to 10^n: [5,51,435,3221,21394,125102,656325,3129429,13760821] — Tom Sirgedas, Mar 20 '24 at 19:28
Oh thank you for the bounty! There is still work to do in this problem. — Dmitry Kamenetsky, Mar 23 '24 at 22:53

Melissa's Numbers

4 Answers4