8
$\begingroup$

I came across the following curious problem while playing around with my calculator.

Take any positive integer $n$; for this example we'll use $216$. Create a sequence as follows:

  • Factor $n$ into its prime factors, listing smaller factors first and expanding exponents; $216=2\times2\times2\times3\times3\times3$
  • Create the next number by concatenating the first $d$ digits of its prime factors, where $d$ is the number of digits in $n$; $2\times2\times2\times3\times3\times3\to222$
  • Repeat until...? $222\to2\times3\times37\to233\to233\to\cdots$

The first thing that is easy to show is that you will always be able to create a $d$-digit number at any step.

The sequence obviously stops once it hits a prime number. But can it stop for any other reason? It turns out that the first number whose sequence does not end in a prime number is $333$, a composite which miraculously generates itself: $333=3\times3\times37\to333$.

A quick computer program found several other numbers that exhibit this property:

  • $2255\to5114\to2255\to\cdots$ a loop!
  • $22222\to24127\to23104\to22222\to\cdots$ a longer loop!
  • $22564\to22564\to\cdots$
  • $31111\to53587\to41130\to23354\to21167\to61347\to31111\to\cdots$ !!!
  • $210526\to210526\to\cdots$
  • $252310\to252310\to\cdots$
  • $1143241\to1143241\to\cdots$
  • $3331233\to3331233\to\cdots$
  • $3710027\to3710027\to\cdots$

Update: up to 150 million, I found

  • $219371601\to367109140\to225183554\to219371601\to\cdots$

I'll call these numbers, whose sequence does not end in a prime, self-factoring numbers. As far I've tested, these are all the self-factoring numbers below forty million.

This topic may have no depth to explore (it may just be a fun mathematical coincidence), but I would still like to pose the following questions:

  • Are these self-factoring numbers related in any way? Can we prove any property about these numbers at all?
  • Is there any property that might help speed up a computer search past the brute force approach?
  • Are there infinitely many such self-factoring numbers? Could there be a constructive proof?
$\endgroup$
  • $\begingroup$ Interesting question! One idea: let $X_d$ be the set of $d$ digit natural numbers and $\phi: \mathbb{N} \rightarrow \mathbb{N}$ be the transformation you've described. Then let $P^n_d = \bigcup_{i = n}^\infty \phi^i[X_d]$. The question you are asking is basically if $\bigcap_{i=1}^\infty P^i_d$ contains any non-primes for any $d$. $\endgroup$ – Bruce Zheng Oct 7 '14 at 21:13
1
$\begingroup$

Similar to $a_0=210526$ is $$a_3=210526315789473684210526315789473684210526315789473684210526$$ where $$a_k=2\cdot\frac{2\cdot10^{18k+6}-3}{19}=210\dots526=2\cdot10\dots5263.$$ In each case $a_k$ is twice a prime. I have checked all the $a_k/2$ for $k=0,\dots,745$ for primality, and not found any further primes (according to GAP 4.7).

Another possible source of similar examples (i.e. where the number self-factors to itself by being twice a prime) is the numbers \begin{align*} b_k&=2\cdot\frac{2\cdot10^{18k+1}-1}{19}=210\dots842=2\cdot10\dots8421, \end{align*} though $b_0=2$ is prime, and $b_k/2$ is composite for $k=1,\dots,739$. Stopping the decimal expansion of $4/19$ anywhere else cannot yield a number that is twice a prime. For example the numbers \begin{align*} 2\cdot\frac{2\cdot10^{18k+11}-9}{19}&=210\dots578=2\cdot10\dots5789 \end{align*} are all multiples of 11, and the numbers \begin{align*} 2\cdot\frac{2\cdot10^{18k+13}-7}{19}&=210\dots894=2\cdot10\dots8947 \end{align*} are all multiples of 13. (For $p=11$ and $p=13$, $p\mid 1001$, so, modulo $p$, $1000=-1$, so $10^6=1$ and $10^{18k}=1$. Thus, if $p$ divides any member of the above sequence, $p$ divides them all.)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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