3
$\begingroup$

The sequence of numbers 49297533, 49297534, and 49297535 is notable, because the prime factorizations of these numbers are each of the form $a^1 \cdot b^1 \cdot c^1 \cdot d^1 \cdot e^1$, and their representations in this form include the first 11 primes:

$$ 3\cdot 19\cdot 23\cdot 31\cdot 1213 = 49,297,533$$ $$ 2\cdot 11\cdot 13\cdot 97\cdot 1777 = 49,297,534$$ $$ 5\cdot 7\cdot 17\cdot 29\cdot 2857 = 49,297,535$$

What is the lowest sequence of numbers $x, x+1, x+2$ such that all 3 numbers are of this "five prime factors" form, and their representations, taken together, include the first 12 primes, $2,3,5,7,11,13,17,19,23,29,31,37$?

Note that 12 would be the largest number of minimal primes one could have in this configuration, since there is a total of 15 primes needed, meaning that with 13 minimal primes included, one of the products would be much smaller than the others.

POSTSCRIPT: I found the smallest group of cardinality 4 (using the 9 smallest primes) reasonably quickly: $$ 11\cdot 13\cdot 17\cdot 9463= 23,004,553 $$ $$ 2\cdot 19\cdot 23\cdot 26321= 23,004,554 $$ $$ 3\cdot 5\cdot 7\cdot 219091 =23,004,555 $$

and for cardinality 3: $$ 3\cdot 11\cdot 113 = 3729 $$ $$ 2\cdot 5\cdot 373 = 3730 $$ $$ 7\cdot 13\cdot 41 = 3731 $$

$\endgroup$
  • 1
    $\begingroup$ When you say "there might not be one", you mean there might be no such x, x+1, x+2 triple that all take the five-prime-factors form and include the first 12 primes? Is there a special reason for choosing those 12? $\endgroup$ – Travelling Salesman Sep 2 '15 at 14:49
  • $\begingroup$ Yes. Every such collection will include 15 unique primes. Thus one can't have more than 12 of the first primes in any such collection, since with e.g. 13 smallest primes, one of the products will have to include 5 of these smallest primes. 12 is thus the largest number of smallest primes that can satisfy these requirements. $\endgroup$ – pgblu Sep 2 '15 at 14:51
  • 1
    $\begingroup$ Including the reasoning in that comment in your Question would improve it. $\endgroup$ – hardmath Sep 2 '15 at 15:27
1
$\begingroup$

15,637,506,729 is the smallest example, based on naive exhaustive search.

$ factor.pl 15637506729 15637506729+1 15637506729+2
15637506729: 3 13 17 37 637459
15637506730: 2 5 19 29 2838023
15637506731: 7 11 23 31 284831

I used this program to make a candidate list, which you could write almost identically in Pari/GP.

perl -Mntheory=:all -E '$|=1; foroddcomposites { if (scalar(factor($_)) == 5 && is_square_free($_) && scalar(factor($_+1)) == 5 && is_square_free($_+1) scalar(factor($_+2)) == 5 && is_square_free($_+2)) { say } } 1e13' > /tmp/1418444.txt

In another window I did:

tail -f /tmp/1418444.txt | perl -Mntheory=:all -nE 'chomp; my %f; for my $c (factor($_),factor($_+1),factor($_+2)) { $f{$c}++ } my $p=1; for my $c (@{primes(37)}) { $p=0 unless $f{$c} } say if $p;'

You could do it all at once, I wanted to see the intermediates and see the examples with the first 11 primes.

Peter got this result earlier, but I started my program later and I went from the bottom rather than top. Oh, and thanks to Peter for his large early result which at least let me know a solution existed (I of course hoped it wouldn't be that large).

$\endgroup$
  • 1
    $\begingroup$ I needed the head-start because of my awfully slowly PARI/GP-program. I have no GNU-compiler, but that should not make such a difference. The version is new (sumdigits finally implemented!) but my computer seems to be already a dino compared to the newer ones. Sigh ... $\endgroup$ – Peter Sep 3 '15 at 15:43
  • $\begingroup$ I am still baffled that the twin primes from $10^{1000}$ to $10^{1000}+10^7$ can be found in two minutes. With all sieves, I still needed some hours ... $\endgroup$ – Peter Sep 3 '15 at 15:45
  • $\begingroup$ Concerning the size of the smallest example : I expected a much larger smallest example. $\endgroup$ – Peter Sep 3 '15 at 15:47
  • $\begingroup$ @Peter I just added sumdigits to my module a couple days ago. :) I'm actually surprised how much faster it is vs.vecsum(split(//,$n)) -- for big inputs, making that list and passing it around is surprisingly time consuming. Re computer, I ran it on a 3930k (released in 2011) with 10 other 100% CPU jobs running. The 3930K has great memory bandwidth and does very well at running lots of tasks at the same time. $\endgroup$ – DanaJ Sep 3 '15 at 16:39
2
$\begingroup$

Using the chinese remainder theorem , I found an example (probably not the smallest)

$n\ :=\ 1,020,776,850,069,689$ with $16$ digits

? print(factor(n))
[23, 1; 29, 1; 31, 1; 37, 1; 1334263361, 1]

? print(factor(n+1))
[2, 1; 3, 1; 5, 1; 7, 1; 4860842143189, 1]

? print(factor(n+2))
[11, 1; 13, 1; 17, 1; 19, 1; 22099998919, 1]

The program which found this solution :

? s=chinese(Mod(2,23*29*31*37),Mod(1,2*3*5*7));s=chinese(s,Mod(0,11*13*17*19));s
=component(s,2);print(s);gef=0;while(gef==0,s=s+t;x2=(s-1)/2/3/5/7;x1=s/11/13/17
/19;x3=(s-2)/23/29/31/37;if(ispseudoprime(x1,2)==1,if(ispseudoprime(x2,2)==1,pri
nt(s,"  ",x3);if(ispseudoprime(x3,2)==1,gef=1))));print(s-2)
4135725600721
308385989127931  403093121
1020776850069691  1334263361
1020776850069689

My current record is

$n=15,637,506,729$

with $11$ digits and the factorizations

? print(factor(n));print(factor(n+1));print(factor(n+2))
[3, 1; 13, 1; 17, 1; 37, 1; 637459, 1]
[2, 1; 5, 1; 19, 1; 29, 1; 2838023, 1]
[7, 1; 11, 1; 23, 1; 31, 1; 284831, 1]
$\endgroup$
  • 2
    $\begingroup$ If this WAS the smallest, that would be a remarkable coincidence, since it happens to be one where the 12 smallest primes are distributed in numerical order! 2-7, 11-19, and 23-37. $\endgroup$ – pgblu Sep 2 '15 at 21:13
  • 1
    $\begingroup$ I have a brute-force algo that I'm deploying in the next few hours, I will report back on my progress. Note that, for all these triples, it's the one in the middle that will contain the divisor 2, so that cuts down on a few cycles. $\endgroup$ – pgblu Sep 2 '15 at 21:19
  • $\begingroup$ The number $15637506729$ is probably the smallest example (See edit for the factorizations) $\endgroup$ – Peter Sep 3 '15 at 8:58
  • $\begingroup$ Wow, Peter, I just got that one this morning too! :-) We'll see what else emerges, though... my program is still running. Now we can devote our energies to finding a more efficient method, if one even exists. $\endgroup$ – pgblu Sep 3 '15 at 11:39
  • $\begingroup$ The chinese remainder theorem is most useful here. If I programmed correct, the given example IS the smallest possible. $\endgroup$ – Peter Sep 3 '15 at 11:58

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.