Ask Your Question
0

A routine for testing a conjecture

asked 2018-12-04 10:47:40 +0200

polistirolo gravatar image

updated 2018-12-11 16:12:08 +0200

The ec numbers are so defined:

ec(k) = (2^k-1)*10^d + 2^(k-1) - 1

where d is the number of decimal digits of 2^(k-1) - 1 . In other words these numbers are formed by the base 10 concatenation of two consecutive Mersenne numbers, for example: 157, 12763, 40952047...

For some values of k, ec(k) is probable prime. I found that up to k=565.000 there is no probable prime of the form (2^k-1)*10^d + 2^(k-1) - 1 which is congruent to 6 mod 7. So I conjectured that there is no probable prime of this form congruent to 6 mod 7. Has somebody an efficient program for Sage to test this conjecture further?

edit retag flag offensive close merge delete

Comments

I guess you can just program it to create these numbers (and probably can use a string concatenation to do so more efficiently than multiplication?). But without some extra theory helping reduce the primality testing like we have for Mersenne numbers, it might be hard to make a test that was "efficient" in the sense you probably mean.

kcrisman gravatar imagekcrisman ( 2018-12-06 17:47:39 +0200 )edit
kcrisman gravatar imagekcrisman ( 2018-12-07 19:36:31 +0200 )edit

1 Answer

Sort by ยป oldest newest most voted
1

answered 2018-12-11 02:03:08 +0200

dan_fulea gravatar image

I tried the following:

sage: R = Zmod(7)
sage: for k in [2..500]:
....:     a = 2^k-1
....:     b = 2^(k-1)-1
....:     N = ZZ('{}{}'.format(a, b))
....:     if R(N) != R(6):
....:         continue
....:     print( "k=%s Is ec(k) prime? %s. Factorization follows:\nec(k) = %s\n"
....:            % (k, N.is_prime(), N.factor()) )
....:     
k=10 Is ec(k) prime? False. Factorization follows:
ec(k) = 19 * 103 * 523

k=11 Is ec(k) prime? False. Factorization follows:
ec(k) = 479 * 42737

k=14 Is ec(k) prime? False. Factorization follows:
ec(k) = 11 * 593 * 25117

k=28 Is ec(k) prime? False. Factorization follows:
ec(k) = 233 * 1607 * 716915680417

k=32 Is ec(k) prime? False. Factorization follows:
ec(k) = 131 * 4463 * 21601 * 44623 * 76213

k=49 Is ec(k) prime? False. Factorization follows:
ec(k) = 5 * 757 * 16333 * 1225015921 * 7433549000531

k=53 Is ec(k) prime? False. Factorization follows:
ec(k) = 5 * 337 * 53455188455436151040711945027

k=70 Is ec(k) prime? False. Factorization follows:
ec(k) = 109 * 839 * 75046613 * 241028036131 * 713694876516226387

k=71 Is ec(k) prime? False. Factorization follows:
ec(k) = 23 * 15737 * 65234886529801619745410789282584431073

k=74 Is ec(k) prime? False. Factorization follows:
ec(k) = 11 * 19 * 269 * 9532513 * 352463140718866450408093341421867

k=88 Is ec(k) prime? False. Factorization follows:
ec(k) = 31 * 73875972467027 * 135137137017690741456718218482342349371

k=92 Is ec(k) prime? False. Factorization follows:
ec(k) = 730315371175567 * 39625364799966331 * 1711101949753493724071011

k=109 Is ec(k) prime? False. Factorization follows:
ec(k) = 5 * 653 * 1606053961 * 10568312139584431 * 11711717200756188938696404879503826537

k=113 Is ec(k) prime? False. Factorization follows:
ec(k) = 5 * 193 * 149270993 * 24073195224569 * 29946980304751014175703201587995219695454299

k=130 Is ec(k) prime? False. Factorization follows:
ec(k) = 1129 * 959806273091 * 7986419296370382549203 * 157278660923445868781899626742322195007583

k=131 Is ec(k) prime? False. Factorization follows:
ec(k) = 51162479 * 2784303036149 * 567204394305177089 * 336916099985640327995882896303775632213517

k=148 Is ec(k) prime? False. Factorization follows:
ec(k) = 76292370683 * 46974096157407024149 * 60514961739327090714406687 * 1645269521635269788991753843968263

k=152 Is ec(k) prime? False. Factorization follows:
ec(k) = 31 * 107 * 677 * 2131 * 145361 * 173087 * 452931678706211 * 6576742625936687 * 159179030364736283121060312673245829294207

k=169 Is ec(k) prime? False. Factorization follows:
ec(k) = 5 * 67360183384144337 * 1317991479336685050851 * 1685712081595174413704015925364267420341119063462133679767171233

k=173 Is ec(k) prime? False. Factorization follows:
ec(k) = 5 * 1543 * 11287 * 1374911658072068607645715891596827336333789380835457971697269244791317892283158474011048315274579

k=190 Is ec(k) prime? False. Factorization follows:
ec(k) = 19 * 82593443886666852155734071357995610738188887427158348853883401985101228162919972298836892542211199706871473911269

and i had to stop here. (Since i did not see any sense in finding prime numbers of this "concatenated shape". This is non-structural mathematics for me.)

edit flag offensive delete link more

Comments

@dan_fulea the program checks primes or probable primes? I am looking for probable primes.

polistirolo gravatar imagepolistirolo ( 2018-12-11 16:11:22 +0200 )edit

@dan_fulea and what if I want to cancel the factorization?

polistirolo gravatar imagepolistirolo ( 2018-12-11 18:18:21 +0200 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

Stats

Asked: 2018-12-04 10:47:40 +0200

Seen: 216 times

Last updated: Dec 11 '18