mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Puzzles

Reply
 
Thread Tools
Old 2021-07-01, 11:54   #1
Xyzzy
 
Xyzzy's Avatar
 
Aug 2002

830610 Posts
Default July 2021

https://www.research.ibm.com/haifa/p.../July2021.html
Xyzzy is offline   Reply With Quote
Old 2021-07-06, 14:53   #2
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

2×1,789 Posts
Default

I've learned some things about Carmichael numbers from researching this puzzle, and unless I've misunderstood something 100 digit primary Carmichael numbers seem to be pretty easy to find. So far the largest I've found is a 620 digit primary solution.
bsquared is offline   Reply With Quote
Old 2021-07-06, 22:10   #3
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

2·1,789 Posts
Default

Quote:
Originally Posted by bsquared View Post
I've learned some things about Carmichael numbers from researching this puzzle, and unless I've misunderstood something 100 digit primary Carmichael numbers seem to be pretty easy to find. So far the largest I've found is a 620 digit primary solution.
A little more optimization and up to a 2470 digit solution. Not searching any more until I hear something from the puzzle admins about whether these solutions are correct.
bsquared is offline   Reply With Quote
Old 2021-07-07, 05:33   #4
tgan
 
Jul 2015

22×7 Posts
Default

did you also find b
"and b is the largest non-trivial square root of unity modulo n."
tgan is offline   Reply With Quote
Old 2021-07-07, 13:03   #5
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

3×1,657 Posts
Default

I submitted a solution on the 2nd in the suggested format. I had never heard of "primary Carmichael numbers." Apparently a new thing. I learned something!

I only submitted a single example, a primary Carmichael number just greater than 10^100 and called it good. Inspired by this thread, I adjusted my script to find one just greater than 10^620.

In theory, my script could find solutions of any size, but in practice it's so mindless it would take a long long time to find a really large solution.
Dr Sardonicus is offline   Reply With Quote
Old 2021-07-07, 13:26   #6
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

2·1,789 Posts
Default

Quote:
Originally Posted by tgan View Post
did you also find b
"and b is the largest non-trivial square root of unity modulo n."
Yes I'm finding them by construction so I know the factors, and knowing those it's straightforward to find the non-trivial roots of unity.

Quote:
Originally Posted by Dr Sardonicus View Post
I submitted a solution on the 2nd in the suggested format. I had never heard of "primary Carmichael numbers." Apparently a new thing. I learned something!

I only submitted a single example, a primary Carmichael number just greater than 10^100 and called it good. Inspired by this thread, I adjusted my script to find one just greater than 10^620.

In theory, my script could find solutions of any size, but in practice it's so mindless it would take a long long time to find a really large solution.
Yeah I've also learned some things - the mark of a good puzzle. Also I lied earlier and kept my script running over night. This morning I saw that it found a solution of size 4936 digits.
bsquared is offline   Reply With Quote
Old 2021-08-11, 11:29   #7
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

3·1,657 Posts
Default

I was dissatisfied with the published solution - in particular, the failure to address the question of being primary. Also, the link in the August puzzle to July's solution doesn't work because it wasn't updated when the solution was posted.

So I'm posting my own solution.

Solution: The example [1729 = 7*13*19] is suggestive, in that it is the smallest of a well known family of 3-factor Carmichael numbers n = p1*p2*p3 where

(*) p1 = 6*k + 1, p2 = 12*k + 1, and p3 = 18*k + 1, k = positive integer. It is easily shown that in this case 36*k divides n - 1, so that when p1, p2, and p3 are all prime, n satisfies Korselt's criterion, so is a Carmichael number.

If p is a prime factor of n, the base-p digits of n are those of n/p, with a zero appended. Here we have

p2 = 2*p1 - 1 and p3 = 3*p1 - 2, so that p2*p3 = 6*p1^2 - 7*p1 + 2, which may be rewritten 5*p1^2 + (p1 - 7)*p2 + 2. Since p1 > 5, the base-p1 digits are 5, p1 - 7, and 2; their sum is p1.

Similarly, p1 = (p2 +1)/2 and p3 = (3*p2 - 1)/2, so that

p1*p3 = (3*p2^2 + 2*p2 - 1)/4 = (3*p2 + 1)/4 *p2 + (p2 - 1)/4; it is easy to see see that (3*p2 + 1)/4 and (p2 - 1)/4 are integers in [0, p2 - 1], hence the base-p2 digits of n/p2, and their sum is p2.

Finally, p1 = (p3 + 2)/3 and p2 = (2*p3 + 1)/3, so p1*p2 = (2*p3^2 + 5*p3 + 2)/9, which may be written (2*p3 - 2)/9 * p3 + (7*p3 + 2)/9. As before, it is easy to see that (2*p3 - 2)/9 and (7*p3 + 2) are the base-p3 digits of p1*p2, and their sum is p3.

Thus, if p1, p2, and p3 as in (*) are all prime, n = p1*p2*p3 is a primary Carmichael number.

Finding a k for which 6*k + 1, 12*k + 1, and 18*k + 1 are all prime such that n > 10^100, computing the square roots of 1 mod n, and finding the largest of these that is not 1 or -1 (mod n) is then a routine matter.

Code:
? {
t=ceil((10^100/6/12/18)^(1/3));
d=5*7*11*13*17*19*23*29*31*37;
for(k=t,t+1000000,
p1=6*k+1;
p2=12*k+1;
p3=18*k+1;
n=p1*p2*p3;if(gcd(n,d)==1&&ispseudoprime(p1)&&ispseudoprime(p2)&&ispseudoprime(p3),
t=k;
break));
p1=6*t+1;
p2=12*t+1;
p3=18*t+1;
s=1;
for(i=0,1,
for(j=0,1,
for(k=0,1,
b=lift(chinese([Mod((-1)^i,p1),Mod((-1)^j,p2),Mod((-1)^k,p3)]));
if(b>s&&b<n-1,s=b))));
print(n);
print(p1,", ",p2,", ",p3);
print(s)
}
10000000000000000000000000000405929367865700162694655745350302085810080768959837103297359653235421369
1185631101496687602002051540762347, 2371262202993375204004103081524693, 3556893304490062806006154622287039
10000000000000000000000000000405920933539047145202227288252787796834022398216461136785946154423067343
?
NOTE: A whole class of polynomials which are products of linear factors automatically produces primary Carmichael numbers when the linear factors are all primes, as proven in this paper.
Dr Sardonicus is offline   Reply With Quote
Old 2021-08-11, 18:01   #8
Alfred
 
Alfred's Avatar
 
May 2013
Germany

1278 Posts
Default

Is it possible to "compute" p2*p3-1 as smallest and n-(p2*p3-1) as largest non-trivial root?

Last fiddled with by Alfred on 2021-08-11 at 18:02
Alfred is offline   Reply With Quote
Old 2021-08-12, 15:03   #9
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

497110 Posts
Default

Quote:
Originally Posted by Alfred View Post
Is it possible to "compute" p2*p3-1 as smallest and n-(p2*p3-1) as largest non-trivial root?


I believe so, yes. With p1, p2, and p3 defined as above, obviously A = p2*p3 - 1 is congruent to -1 (mod p2 and mod p3), and is easily shown to be congruent to 1 (mod p1).

The "trivial" square roots of 1 are congruent to 1, or congruent to -1 modulo all of p1, p2, and p3.

Scribbling with paper and pencil, I found that B = 8*p1*p3 + 1 is congruent to 1 (mod p1 and mod p3) and congruent to -1 (mod p2). Similarly, C = 9*p1*p2 - 1 is congruent to -1 (mod p1 and mod p2) but congruent to 1 (mod p3). Clearly 1 and n-1; A and n - A; B and n - B; and C and n - C are all the square roots of unity (mod n).

Now A < n - A, B < n - B, and C < n - C. Also, from the formulas it is clear that A < B and A < C.

EDIT: I was a bit careless. The inequality B < n - B is only valid if p2 > 16, which is not the case with k = 1 (p1 = 7, p2 = 13, p3 = 19).

Last fiddled with by Dr Sardonicus on 2021-08-12 at 17:47
Dr Sardonicus is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
July 2020 tgan Puzzles 6 2020-08-31 11:30
July 2016 Xyzzy Puzzles 4 2016-08-06 22:51
July 2015 Xyzzy Puzzles 16 2015-08-19 16:13
July 2014 Xyzzy Puzzles 6 2014-11-02 19:05
Happy July 4th LaurV Lounge 8 2012-07-06 00:13

All times are UTC. The time now is 02:35.


Mon Oct 18 02:35:14 UTC 2021 up 86 days, 21:04, 0 users, load averages: 1.14, 1.45, 1.42

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.