Hyper Fake Chocolate Number
Time limit1sMemory limit1024 MB
Find 11 primes between 10^7 and 10^8 whose product is a Carmichael number, so that a^(N-1) mod N is 1 for every base a coprime to N.
- Level
Medium7 of 10
- Topics
- Number theory, Math
- Solved
- No attempts yet
Problem
Coco, who loves chocolate and number games, defined a "chocolate number" as follows.
- A positive integer is a chocolate number if it is divisible only by and itself.
Soon after, Coco discovered "Coco's theorem."
- If is a chocolate number, then for every integer coprime to .
Coco then came up with a way to test whether a number is a chocolate number using this theorem. The method is as follows.
- If for every integer coprime to , then is a chocolate number.
However, not long after, Coco found that 561 satisfies this test but is not a chocolate number. Coco called such numbers "fake chocolate numbers" and began studying how to find them.
Neglecting the chocolate factory, Coco focused on this research. Coco found fake chocolate numbers that are products of 3, 4, ..., 10 chocolate numbers, but could not find one that is a product of 11. Finding any one is not hard, so find a number that satisfies the following condition.
- Write . Then is a fake chocolate number, and for each , is a chocolate number with .
Input
There is no input.
Output
Write the 11 chocolate numbers whose product satisfies the condition above on the first line, in ascending order, separated by spaces.