29
$\begingroup$

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 (A371862 in the OEIS). What about nine? And if not, what is the longest sequence of consecutive numbers all of which are Melissa's numbers?

Improve this question
$\endgroup$
15
  • 6
    $\begingroup$ @CrSb0001 70 is a one of Melissa's Numbers! $\endgroup$
    – Bernardo Recamán Santos
    Commented Mar 13 at 16:40
  • 3
    $\begingroup$ 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$.... $\endgroup$
    – Greg Martin
    Commented Mar 16 at 19:40
  • 3
    $\begingroup$ +1 because I had to make the score a Melissa number . . . $\endgroup$
    – geometrian
    Commented Mar 18 at 7:12
  • 2
    $\begingroup$ @DmitryKamenetsky The Melissa number $16384$ can only be done with exactly $14$ factors. $\endgroup$
    – user88375
    Commented Mar 20 at 18:37
  • 2
    $\begingroup$ @BernardoRecamánSantos I have updated my answer. I believe there are infinitely many quadruples of consecutive Melissa numbers :) $\endgroup$
    – Dmitry Kamenetsky
    Commented Mar 21 at 14:36

4 Answers 4

Reset to default
19
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ 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. $\endgroup$
    – Alex Ravsky
    Commented Mar 15 at 19:03
  • 2
    $\begingroup$ @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. $\endgroup$
    – user88375
    Commented Mar 15 at 20:37
15
$\begingroup$

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

Improve this answer
$\endgroup$
6
  • 1
    $\begingroup$ Makes me wonder if you'll also find a length-8 run below 10⁸ and a length-9 run below 10⁹. $\endgroup$
    – Oliphaunt
    Commented Mar 14 at 9:12
  • 2
    $\begingroup$ 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. $\endgroup$
    – Oliphaunt
    Commented Mar 14 at 9:20
  • 5
    $\begingroup$ @Oliphaunt Update: Searched to $10^9$, didn't even find a length-8 run. $\endgroup$
    – isaacg
    Commented Mar 14 at 21:57
  • 2
    $\begingroup$ @DialFrost Added the repository $\endgroup$
    – isaacg
    Commented Mar 15 at 1:44
  • 5
    $\begingroup$ 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 $\endgroup$
    – SE - stop firing the good guys
    Commented Mar 15 at 5:20
11
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 7
    $\begingroup$ 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 $\endgroup$
    – No Name
    Commented Mar 14 at 4:56
6
+50
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • 3
    $\begingroup$ also length 6 starting at 288118221818 $\endgroup$
    – Tom Sirgedas
    Commented Mar 20 at 19:26
  • 3
    $\begingroup$ number of Melissa numbers less than or equal to 10^n: [5,51,435,3221,21394,125102,656325,3129429,13760821] $\endgroup$
    – Tom Sirgedas
    Commented Mar 20 at 19:28
  • $\begingroup$ Oh thank you for the bounty! There is still work to do in this problem. $\endgroup$
    – Dmitry Kamenetsky
    Commented Mar 23 at 22:53

Not the answer you're looking for? Browse other questions tagged or ask your own question.