[Community Puzzle] Carmichael numbers

Puzzles
#1

Coding Games and Programming Challenges to Code Better

Send your feedback or ask for help here!

#2

In the puzzle description, a constraint is stated:

1⩽n⩽100000

However test case 6 uses n = 449065.

I’m guessing the constraint should be 1,000,000 (six zeroes instead of five) but it should be changed, as I chose my algorithm based on the existing constraint.

#3

Hrm you’re right. :blush:

#4

You’re right (sorry about that :frowning:). But in this case, the most naive looping algorithm in a slow interpreted language is amply sufficient (i.e. on a modern machine, 10^5 or 10^6 does not make a big difference even for python).

On second thought, however, it could be really interesting to have “Carmichael Numbers Redux” puzzle, where one would have to implement some more advanced algorithms (cf. e.g. Wikipedia; it looks like a basic cryptography-related exercice). Actually, as you remarked, it’s enough to increase the upper bound and deal with bigger numbers.

The only delicate question here is to get the range of the numbers right – so that one couldn’t break it by brute force (even in c++) and yet one could solve it in a scripting language with a smart algorithm.

If some others find such a puzzle interesting, just let me know here and I’ll do some testing to find the right numbers. :sunglasses: What do you think?

#5

Yeah, but I was cheating. :wink: I got a list of all the numbers below 100000 and was just checking against them. So really no algorithm. Now I have to find a real one.

#6

Hi
I think the problem statement of the “Carmichael numbers” puzzle has a mistake.
“There are numbers, called Carmichael numbers, that are not prime but for which the equality remains true for any integer a.”
taken from the puzzle.
“… for all integers 1<b<n which are relatively prime to n.”
taken from wikipedia.

#7

Hi. I have some troubles with submit test Bigger composite number.
I have ideas, why it so bad.
Idea #1
it’s real big composite number and program stops, during the time out.
Idea #2
May be there is something wrong in my solution.

i find prime factors for number. Check condition that n and prime factors %2==0.
Check that n-1%pr.fact.-1==0

Can someone say what is wrong?

#8

I’m guessing with ‘Check condition that n and prime factors %2==0’ you mean 1 at the end, but in any case, if you’re trying to use Korselt’s criterion you need to check the number is square-free (e.g. 27 satisfies oddness and 26%2==0, but is not a Carmichael number).

#9

“I’m guessing with ‘Check condition that n and prime factors %2==0’ you mean 1 at the end, but in any case, if you’re trying to use Korselt’s criterion you need to check the number is square-free (e.g. 27 satisfies oddness and 26%2==0, but is not a Carmichael number).”

edit p.f.%2!=0
if problem was with this condition, i’m not passed tests in IDE

#10

Yeah, I gathered that bit was a typo; read the rest of my post – I think the problem is that you are not testing for square-freeness.

#11

Add
if(i!=0&&i!=1&&i<65535&&n%(i*i)==0)
{
alarm=1;
}
where i - variable in a loop
n- number
condition i<65535 because if i>65535 apears mistake DivideByZeroException
alarm - variable that in beging is 0, if some of conditions are not passed alarm became 1 and
in the end we write NO

EDIT change int type to long. there is no mistake. but submit test still fail

#12

Is it timing out or displaying yes? If former, you can speed up the above, if latter, you could try, instead of getting an input, looping over the integers upwards and seeing which numbers are erroneously identified as Carmichael numbers (i.e. print these out), then work from there. With the squarefreeness (assuming you kept in the other criteria), the conditions you need should be there, and it might just be a silly typo somewhere.

#13

thanks
i think something was with prime numbers. and also if you work with big numbers and want to check condition that n has no squares use type long.

#14

My naive check fails because a^n goes integer overflow. Is there any math theorem which can help, or the intention was having to implement unlimited length integer operations using strings?

#15

When you want to compute a^n mod m, use modular exponentiation by squaring.

#16

Thanks. This solved the integer overflow problem, but the naive test still timeouted at the big Carmichael number test. My son came to rescue suggesting Korselt’s criterion which was just the time-saving theorem I was looking for and it did the trick for me… :slight_smile: