Showing posts with label right. Show all posts
Showing posts with label right. Show all posts

Saturday, 7 January 2023

Forming Large Primes

 I was surprised to come across the tweet shown in Figure 1 from Fermat's Library:


Figure 1: permalink

While this is surprising enough, it's also interesting that, whether we are counting down from 82 or counting up from 1, none of the intermediate numbers is prime. The prime has 155 digits. However, if the digits are removed or added one by one, then there are two intermediate primes (permalink). These are:

746454443424140393837363534333231302928272625242322212019181716151413121110987654321

21110987654321

If we start adding the numbers to the right of the 1 instead of to the left, it has been shown that no primes exist up to \(n\)=344869 (see comments to OEIS A007908). The search for such a prime formed in this manner is continuing. 

This got me thinking about other ways to create large primes, starting from 1 each time. What if we add only prime numbers to the left or right. How long before a prime is created? 


ADDING ONLY PRIMES TO THE LEFT

Well, let's starting adding primes to the left of 1 up to a limit of 1000. This what I found (permalink):

231917131175321 with 15 digits

41373129231917131175321 with 23 digits

898379737167615953474341373129231917131175321 with 45 digits


ADDING ONLY PRIMES TO THE RIGHT

What if the primes are added to the right of the 1? This is the result (permalink):

1235711 with 7 digits

123571113171923 with 15 digits


ADDING ONLY ODD NUMBERS TO THE LEFT

What if we add only odd numbers to the left of the 1? This is the result (permalink):

31 with 2 digits

737169676563615957555351494745434139373533312927252321191715131197531 with 69 digits

12312111911711511311110910710510310199979593918987858381797775737169676563615957555351494745434139373533312927252321191715131197531 with 131 digits


ADDING ONLY ODD NUMBERS TO THE RIGHT

What if we add the odd numbers to the right of the 1? Here are the results (permalink):

13 with 2 digits

135791113151719 with 15 digits

135791113151719212325272931 with 27 digits

135791113151719212325272931333537394143454749515355575961636567 with 63 digits

135791113151719212325272931333537394143454749515355575961636567697173757779818385878991939597 with 93 digits

This investigation is never-ending so I'll stop there but counting down from 82 to 1 still holds the record for the longest prime at 155 digits. The permalinks above can be easily modified to investigate other variations.

Tuesday, 15 March 2022

Truncatable Primes

I've not dedicated a post to truncatable primes since I started this blog in 2015 but I was prompted to do so because one of the properties associated with my diurnal age today, 26644, is that it's a member of OEIS A346662:


  A346662

Number of \(n\)-digit left- or right-truncatable primes with no consecutive zero digits.   


The number of members of this sequence is finite and consists of:

4, 16, 76, 300, 955, 2648, 6402, 14339, 28684, 53450, 91284, 147064, 221301, 319067, 433227, 567565, 700765, 834464, 947055, 1050886, 1114368, 1157526, 1150645, 1117265, 1044757, 963722, 855804, 753172, 633786, 528122, 426328, 339866, 264078, 202013, 150330, 111055, 78996, 56123, 38874, 26644, 17944, 11898, 7878, 4945, 3255, 2024, 1323, 764, 464, 286, 158, 77, 40, 26, 14, 5, 5, 4, 1, 1

The sequence member 26644 corresponds to \(n\)=40. Thus there are 26644 40-digit primes that are left-or right-truncatable. The reason for having no consecutive zero digits is that, without this restriction, suitable primes could be made indefinitely long. The comments to the OEIS entry are as follows:
A left- or right-truncatable prime is a prime number from which one digit at a time may be removed from the left or right end until a single-digit prime is reached, with each digit removal resulting in a prime. There exists only one such 60-digit prime: 
202075909708030901050930450609080660821035604908735717137397 
Since it cannot be extended, there are no such primes with more than 60 digits, so a(60)=1 is the final term of the sequence.

The OEIS sequence listing these primes is A347864:


 A347864

Left-or right-truncatable primes, restricted to one consecutive zero.      

The sequence begins as follows:

2, 3, 5, 7, 13, 17, 23, 29, 31, 37, 43, 47, 53, 59, 67, 71, 73, 79, 83, 97, 103, 107, 113, 131, 137, 139, 167, 173, 179, 197, 223, 229, 233, 239, 271, 283, 293, 307, 311, 313, 317, 331, 337, 347, 353, 359, 367, 373, 379, 383, 397, 431, 433, 439, 443, 467, 479, 503 

The OEIS comments state that:

There are 16,484,138 primes in this list, in total. The largest one has 60 digits and there is only one of that length.

Generally however, when considering truncatable primes, zeros are not allowed at all. One such OEIS sequence with this restriction is OEIS A137812:

 
 A137812

Left- or right-truncatable primes.                                                     


This finite sequence begins as follows:

2, 3, 5, 7, 13, 17, 23, 29, 31, 37, 43, 47, 53, 59, 67, 71, 73, 79, 83, 97, 113, 131, 137, 139, 167, 173, 179, 197, 223, 229, 233, 239, 271, 283, 293, 311, 313, 317, 331, 337, 347, 353, 359, 367, 373, 379, 383, 397, 431, 433, 439, 443, 467, 479, 523, 547, 571, ...

For example, 313 --> 13 --> 3 or 313 --> 31 --> 3. Another example is 443 --> 43 --> 3. Note that this sequence lists the actual primes and not the number of possible \(n\)-digit primes. The OEIS comments state that:
Repeatedly removing a digit from either the left or right produces only primes. There are 149,677 terms in this sequence, ending with a 31 digit prime: 
8939662423123592347173339993799

In the previous process, we have the option of successively moving one digit from the left OR right but different constraints can be imposed. Three of these are:

  1. digits can only be removed from the left (this produces the left-truncatable primes)
  2. digits can only be removed from the right (this produces the right-truncatable primes)
  3. digits must be removed in pairs (one from the left and one from the right, simultaneously)
The left-truncatable primes comprise OEIS  A024785: 


 A024785

Left-truncatable primes: every suffix is prime and no digits are zero.      


An example is 1223 because 1223, 223, 23 and 3 are all prime. There are 4620 such primes, the largest being 357686312646216567629137. The sequence begins:

2, 3, 5, 7, 13, 17, 23, 37, 43, 47, 53, 67, 73, 83, 97, 113, 137, 167, 173, 197, 223, 283, 313, 317, 337, 347, 353, 367, 373, 383, 397, 443, 467, 523, 547, 613, 617, 643, 647, 653, 673, 683, 743, 773, 797, 823, 853, 883, 937, 947, 953, 967, 983, 997, 1223, ...

The right-truncatable primes comprise OEIS A024770:


 A024770

Right-truncatable primes: every prefix is prime.                                                   


An example is 31193 because 31193, 3119, 311, 31 and 3 are all prime. There are 83 such primes, the largest being 73939133. The sequence begins:

2, 3, 5, 7, 23, 29, 31, 37, 53, 59, 71, 73, 79, 233, 239, 293, 311, 313, 317, 373, 379, 593, 599, 719, 733, 739, 797, 2333, 2339, 2393, 2399, 2939, 3119, 3137, 3733, 3739, 3793, 3797, 5939, 7193, 7331, 7333, 7393, 23333, 23339, 23399, 23993, 29399, 31193, ...

There are 15 primes that are both left- and right-truncatable and form OEIS A020994:
2, 3, 5, 7, 23, 37, 53, 73, 313, 317, 373, 797, 3137, 3797, 739397

The bi-truncatable primes comprise OEIS A077390:


  A077390

Primes which leave primes at every step if most significant digit and least significant digit are deleted until a one digit or two digit prime is obtained.

An example is 21313 because 21313, 131 and 3 all are primes. The sequence begins:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 127, 131, 137, 139, 151, 157, 173, 179, 223, 227, 229, 233, 239, 251, 257, 271, 277, 331, 337, 353, 359, 373, 379, 421, 431, 433, 439, 457, 479, 521, 523, 557, 571, 577, 631, 653, 659, ...

The OEIS comments state that:
There are exactly 920,720,315 such primes, the largest being 9161759674286961988443272139114537477768682563429152377117139 1111313737919133977331737137933773713713973.

There are exactly 331,780,864 odd length primes and 588,939,451 even length primes, the largest odd length prime being

7228828176786792552781668926755667258635743361825711373791931117197999133917737137399993737111177