12

3

Take a natural number's prime factors and list them increasingly and repeating them according to multiplicity. Concatenate their decimal (or in any base) representation to get a new number and repeat the process. Does this always end in a prime number for any input?

flag
What do you mean by concatenate? So for example for 12, the prime factor are 2,2,3. The obvious meaning would result in the number 223. But this process will never stop. – Owen Sizemore Jul 11 2010 at 13:26
3 
 @Owen, that's the question: can you show that 12, 223 never stops? 223 is prime. @Franklin: there is no evidence (and no motivation!) for your question, especially because you claim that any base works. 77 (base 10) produces a very long sequence... – Wadim Zudilin Jul 11 2010 at 13:30
So: $4=2.2 \to 22 =2.11\to 211$ prime!! Have you written a program to do this? Does the chosen base matter? – supercooldave Jul 11 2010 at 13:30
@Wadim: I agree. The better question would be to establish a heuristic based on the probability of primality of n being 1/log n, and the "normal" behaviour of prime factorisations. – Charles Matthews Jul 11 2010 at 14:10
2 
 The independence of the base is that the question asks is for some number, in some base, the sequence never stops. Notice, for example that the remainders of the numbers appearing in the sequences (except the first one) in the division by the base (i.e. the last digit) correspond to possible last digits in that base. I have put a computer to run it in base 10 and all numbers end so far. Motivation? Just fun so far. – Franklin Jul 11 2010 at 14:21
show 1 more comment

2 Answers

16

It's open problem, sequence A037274 from OEIS, so-called "home primes". Hm, the value for n=77 is even unknown.

P.S. On-Line Encyclopedia of Integer Sequences definitely should be included in FAQ.

link|flag
What does the Conways comment mean? "Probabilistic arguments give exactly zero for the chance that the sequence of integers starting at n contains no prime, the expected number of primes being given by a divergent sequence - John Conway (conway(AT)math.princeton.edu)" He said exactly zero? Is it them proven? – Franklin Jul 11 2010 at 14:30
2 
 It means that if we will use non-rigorous arguments, then we can deduce that for every initial number this sequence ends in a prime number. But, it's not a proof. – Nurdin Takenov Jul 11 2010 at 14:43
10 
 No, it doesn't: "happens with probability zero" is not the same as "never happens." – JBL Jul 11 2010 at 15:49
2 
 Also: "Probability" not always refers to the stochastic interpretation as measure space with $\mu(\Omega)=1$. When talking about subsets of $\mathbb{N}$ it seems to be very common to call the density $\lim_{n\to\infty}\frac{|A\cap\{1,\ldots,n\}|}{n}$ (if it exists) the probability of a natural number being in $A$. – Johannes Hahn Jul 11 2010 at 23:31
1 
 whoops & whoops – Franklin Jul 12 2010 at 16:59
show 1 more comment
6

Is too long for comment: $\ddot\smile$

77
711
3379
31109
132393
344131
1731653
71143523
11115771019
31135742029
717261644891
11193431873899
116134799345907
3204751189066719
31068250396355573
62161149980213343
336906794442245927
734615161567701999
31318836286194043641
333431436916146111627309
33205716184556772142207827
31367222155734752971376323127
733915126325777821480557336017
476734743112036198712947236602187
377171280957470909577133234490256751
3096049809383121823389214993262890297
73796236325118712936424989555929478399
13118114526141133089538087518197265265053
319521441731977174163487542111577539726749
595415617656474189392601483764603009147911
13842314669573706744784027901056001426046777
3129192501509379967095393172011476342474406759
3203927133121399320591151296378525102203388346189
133119651853912195249113288820301002347322382772769
11103725795898241052711667094407302642807490159301277
1152194718705941109372661574127837007959097317735411121
6318653972357749718234812726673333988788742328093848793
711111311391974493533533521186754240313734089696843349346661
3771113711016948131790459407678947892694155341923379077407684653
7310113562312583178332057129971031882457634609852680847686251943317
3111197172271564982895268105721087453190074064393495190773755017652247
373111539295698434141591345095168649790005875768086611455076505611166279
33333711151101316117103176926136887884135060403955118931001222053567659972075047
37987951744462008749649348751784002342702203325604103216176784227054268232116293
................

Although in this specific example there is still a chance to arrive at a prime number, the heuristic is against this conclusion as the length of record increases while prime numbers appear "rarer".

link|flag
Let's not duplicate effort: factordb.com/… I disagree on your heuristic, though. The numbers get larger so the chance of a particular number being prime decreases, but the chance of getting one eventually seems quite good. Of course for many examples it will be far beyond what we can calculate... – Charles Jul 11 2010 at 23:10
Charles, as far as I understand Conway's heuristic, you are right. I was trying to produce an evidence to myself for the fact that any sequence eventually stops. 77 and 300 do not (experimentally, of course), so I indicated my doubts. In any case, the problem looks less treatable than $3x+1$, because the corresponding dynamics can be hardly described. – Wadim Zudilin Jul 12 2010 at 0:17
8 
 Here is the vague heuristic. Factoring into $r$ primes appends about $r$ digits. The typical number of prime factors of a number of size $N$ (or $\log N$ digits) is $\log\log N$. The idea is that if we start with a number of $k$ digits, it will be typically mapped to one with about $k+\log k$ digits. Iterating the size function in digits is around $F(t)=k+t\log kt$ at the $t$th iterate, as the $t$ dominates. The chance of a number with $D$ digits being prime is about $1/D$. Summing $1/F(t)$ over $t$ diverges. This is rough and I ignore constants through it. – Junkie Jul 12 2010 at 0:55
Thanks, Junkie! It's indeed a vague argument but it can be developed into some kind of rigorous heuristic. – Wadim Zudilin Jul 12 2010 at 1:34

Your Answer

Get an OpenID
or

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