Sn1b Primes 

? Czeslaw Koscielny 2007 

Academy of Management in Legnica, Poland, 

Faculty of Computer Science,  

Wroclaw University of Applied Informatics, Poland 

e mail: c.koscielny@wsm.edu.pl 

Abstract 

    The worksheet  concerns particular primes numbers which can be written down  by means of the sequences of ones using positional representation with an arbitrary base. 

1. Introduction 

    Recall that Mersenne prime is the prime number of the form 2ⁿ-1, where n must itself be prime. A  prime number is  the natural number that has only two distinct natural number divisors: 1 and itself. But 

(111...1) 

i.e. Mersenne prime in binary notation is represented as sequence of ones, , where  

 

 

 

since today only 44 Mersenne primes are known and it is unrecognized whether there are infinitely many of them. 

 

2. Teodorczuk Primes 

    My friend, MSc  in electronics, Andrzej Teodorczuk, observed that in decimal notation the number 11 is prime, but numbers 111, 1111, 11111 are not. He wanted to find the nearest "all ones" prime, thus, by means of Maple we easily computed that a decimal number in form of ones, {2, 19, 23, 317, 1031} is prime. I think that such primes deserves to be named Teodorczuk primes. It also can be easily verified that the next Teodorczuk prime, which probably exists, will be written down by means of more than 5000 digits. 

 

3. A Definition of Prime 

   Let the sequence of symbols 0, 1, 2, ..., represent the successive units of the number written down in positional notation with base The prime  is the prime number of the form 

 

(111...1) 

 

where is prime. In other words prime is the prime number represented in base positional notation by means of  the sequence of ones ( stands for "sequence of '1's  representing a number in positional notation base ") . Therefore, primes represent an ulimited class od prime numbers, containing both Mersenne and  Teodorczuk primes. 

 

4. Computing Primes Using Maple 

    To begin the exploration of primes we can use the routine 

 

>	sn1b := proc(b, nmin, nmax::posint) local k, s, es;   k := nmin; es := {};   while k < nmax do      s := (b^k - 1)/(b - 1);      if isprime(s) then        es := es union {k}      end if;    k := nextprime(k);      end do;    es end proc:

 

 

where the parameters b,  nmin and nmx denote the base and the minimal and maximal values of the number of ones representing the prime, respectively. The procedure returns the set prime numbers, for which the number  (1) , represented by means of ones, is prime. For example, the statement 

 

>	sn1_3 := sn1b(3, 1, 2000);

 

(4.1)

 

 

computes the set sn1_3 allowing to determine first 9 primes for base 3. They are the following: 

 

>	for i to 9 do sum(3^k, k = 0 .. sn1_3[i]-1): isprime(%); end do;

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

(4.2)

 

 

Next we compute several first primes for bases from 2 to 100: 

 

>

t := time(): printf("The sets of lengths of sequences of ones, \n"); printf("shorter than 1000, representing Sn1b primes,\n"); printf("for bases from 2 to 100\n"); for i to 99 do  x := sn1b(i+1, 1, 1000);  printf("%s%d%s%s","sn1b_", i+1, " = ",cat(convert(x,string),"\n")) end do: printf("Computed in %7.2f%s", time() - t, " seconds"):

 

The sets of lengths of sequences of ones, shorter than 1000, representing Sn1b primes, for bases from 2 to 100

 

sn1b_2 = {2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127, 521, 607}

 

sn1b_3 = {3, 7, 13, 71, 103, 541}

 

sn1b_4 = {2}

 

sn1b_5 = {3, 7, 11, 13, 47, 127, 149, 181, 619, 929}

 

sn1b_6 = {2, 3, 7, 29, 71, 127, 271, 509}

 

sn1b_7 = {5, 13, 131, 149}

 

sn1b_8 = {3}

 

sn1b_9 = {}

 

sn1b_10 = {2, 19, 23, 317}

 

sn1b_11 = {17, 19, 73, 139, 907}

 

sn1b_12 = {2, 3, 5, 19, 97, 109, 317, 353, 701}

 

sn1b_13 = {5, 7, 137, 283, 883, 991}

 

sn1b_14 = {3, 7, 19, 31, 41}

 

sn1b_15 = {3, 43, 73, 487}

 

sn1b_16 = {2}

 

sn1b_17 = {3, 5, 7, 11, 47, 71, 419}

 

sn1b_18 = {2}

 

sn1b_19 = {19, 31, 47, 59, 61, 107, 337}

 

sn1b_20 = {3, 11, 17}

 

sn1b_21 = {3, 11, 17, 43, 271}

 

sn1b_22 = {2, 5, 79, 101, 359, 857}

 

sn1b_23 = {5}

 

sn1b_24 = {3, 5, 19, 53, 71, 653, 661}

 

sn1b_25 = {}

 

sn1b_26 = {7, 43, 347}

 

sn1b_27 = {3}

 

sn1b_28 = {2, 5, 17, 457}

 

sn1b_29 = {5, 151}

 

sn1b_30 = {2, 5, 11, 163, 569}

 

sn1b_31 = {7, 17, 31}

 

sn1b_32 = {}

 

sn1b_33 = {3, 197}

 

sn1b_34 = {13}

 

sn1b_35 = {313}

 

sn1b_36 = {2}

 

sn1b_37 = {13, 71, 181, 251, 463, 521}

 

sn1b_38 = {3, 7, 401, 449}

 

sn1b_39 = {349, 631}

 

sn1b_40 = {2, 5, 7, 19, 23, 29, 541, 751}

 

sn1b_41 = {3, 83, 269, 409}

 

sn1b_42 = {2}

 

sn1b_43 = {5, 13}

 

sn1b_44 = {5, 31, 167}

 

sn1b_45 = {19, 53, 167}

 

sn1b_46 = {2, 7, 19, 67, 211, 433}

 

sn1b_47 = {127}

 

sn1b_48 = {19, 269, 349, 383}

 

sn1b_49 = {}

 

sn1b_50 = {3, 5, 127, 139, 347, 661}

 

sn1b_51 = {}

 

sn1b_52 = {2, 103, 257}

 

sn1b_53 = {11, 31, 41}

 

sn1b_54 = {3, 389}

 

sn1b_55 = {17, 41, 47, 151, 839}

 

sn1b_56 = {7, 157}

 

sn1b_57 = {3, 17, 109, 151, 211, 661}

 

sn1b_58 = {2, 41}

 

sn1b_59 = {3, 13, 479}

 

sn1b_60 = {2, 7, 11, 53, 173}

 

sn1b_61 = {7, 37, 107, 769}

 

sn1b_62 = {3, 5, 17, 47, 163, 173, 757}

 

sn1b_63 = {5}

 

sn1b_64 = {}

 

sn1b_65 = {19, 29, 631}

 

sn1b_66 = {2, 3, 7, 19}

 

sn1b_67 = {19, 367}

 

sn1b_68 = {5, 7, 107, 149}

 

sn1b_69 = {3, 61}

 

sn1b_70 = {2, 29, 59, 541, 761}

 

sn1b_71 = {3, 31, 41, 157}

 

sn1b_72 = {2, 7, 13, 109, 227}

 

sn1b_73 = {5, 7}

 

sn1b_74 = {5, 191}

 

sn1b_75 = {3, 19, 47, 73, 739}

 

sn1b_76 = {41, 157, 439, 593}

 

sn1b_77 = {3, 5, 37}

 

sn1b_78 = {2, 3, 101, 257}

 

sn1b_79 = {5, 109, 149, 659}

 

sn1b_80 = {3, 7}

 

sn1b_81 = {}

 

sn1b_82 = {2, 23, 31, 41}

 

sn1b_83 = {5}

 

sn1b_84 = {17}

 

sn1b_85 = {5, 19}

 

sn1b_86 = {11, 43, 113, 509}

 

sn1b_87 = {7, 17}

 

sn1b_88 = {2, 61, 577}

 

sn1b_89 = {3, 7, 43, 47, 71, 109, 571}

 

sn1b_90 = {3, 19, 97}

 

sn1b_91 = {}

 

sn1b_92 = {439}

 

sn1b_93 = {7}

 

sn1b_94 = {5, 13, 37}

 

sn1b_95 = {7, 523}

 

sn1b_96 = {2}

 

sn1b_97 = {17, 37}

 

sn1b_98 = {13, 47}

 

sn1b_99 = {3, 5, 37, 47, 383}

 

sn1b_100 = {2} Computed in 1897.25 seconds

 

 

It can be seen that there are not  primes represented by less than 1000 'ones' for bases 9, 25, 32, 49, 51, 64, 81, 91. Therefore, let us search the longer    primes for these bases: 

 

>	t := time(): for k in [9, 25, 32, 49, 51, 64, 81, 91] do   s := sn1b(k, 1001, 3000);    printf("%s%d%s", "sn1b_", k, cat(" = ", convert(s, string),"\n")) end do: printf ("Computed in %7.2f%s", time() - t, " seconds"):

 

sn1b_9 = {}

 

sn1b_25 = {}

 

sn1b_32 = {}

 

sn1b_49 = {}

 

sn1b_51 = {}

 

sn1b_64 = {}

 

sn1b_81 = {}

 

sn1b_91 = {} Computed in 4976.88 seconds

 

 

The patient reader may try to invoke the procedure sn1b once again with grater values of actual parameters nmin  and nmax. 

 

Here are similar computations for bases from 1000 to 1100: 

 

>

t := time(): printf("The sets of lengths of sequences of ones, \n"); printf("shorter than 300, representing Sn1b primes,\n"); printf("for bases from 1000 to 1010\n"); for i to 11 do  x := sn1b(i+999, 1, 300);  printf("%s%d%s%s","sn1b_", i+999, " = ",cat(convert(x,string),"\n")) end do: printf ("Computed in %7.2f%s", time() - t, " seconds"):

 

The sets of lengths of sequences of ones, shorter than 300, representing Sn1b primes, for bases from 1000 to 1010

 

sn1b_1000 = {}

 

sn1b_1001 = {3}

 

sn1b_1002 = {3, 31}

 

sn1b_1003 = {11, 47, 101, 109, 137}

 

sn1b_1004 = {}

 

sn1b_1005 = {}

 

sn1b_1006 = {13}

 

sn1b_1007 = {3, 5}

 

sn1b_1008 = {2, 31, 89, 157}

 

sn1b_1009 = {5}

 

sn1b_1010 = {19} Computed in   12.89 seconds

 

>	t := time(): for k in [1000, 1004, 1005] do   s := sn1b(k, 301, 1000);    printf("%s%d%s", "sn1b_", k, cat(" = ", convert(s, string),"\n")) end do: printf ("Computed in %7.2f%s", time() - t, " seconds"):

 

sn1b_1000 = {}

 

sn1b_1004 = {431, 727, 751}

 

sn1b_1005 = {} Computed in  261.80 seconds

 

5. Conclusion 

    It has been shown how to begin the exploration of a new class of prime numbers, related to Mersenne primes. Considered problems may have some usefulness in the number theory and cryptography.        

Reference 

GIMPS Home Page: http://www.mersenne.org/ 

Legal Notice: The copyright for this application is owned by the author(s). Neither Maplesoft nor the author are responsible for any errors contained within and are not liable for any damages resulting from the use of this material. This application is intended for non-commercial, non-profit use only. Contact the author for permission if you wish to use this application in for-profit activities.