<jupyter_start><jupyter_text>Euler Project Problem 407 - IndempotentsIf we calculate $a^2 mod 6$ for $0 ≤ a ≤ 5$ we get: $0,1,4,3,4,1$.The largest value of a such that $a^2 ≡ a mod 6$ is $4$.Let's call $M(n)$ the largest value of $a < n$ such that $a^2 ≡ a (mod n)$.So $M(6) = 4$.Find $∑ M(n)$ for $1 ≤ n ≤ 10^7$. Analysis:Lets consider all values of $a$ for a given $N$, not just the largest $a<n$.if $a^2 ≡ a (mod n)$, then:$$a(a-1) = kn$$ for some integer, k.<jupyter_code>from EulerFunctions import primelist, primeFactors, factors, is_prime
primes = primelist(10000)
def all_idempotents(n):
    # returns all values of a for a given n.
    out = []
    for a in range(1, n):
        if a**2%n == a:
            out.append(a)
    return out
N = 500
for i in range(1, N):
    all_a = all_idempotents(i)
    print(i, all_a)<jupyter_output>1 []
2 [1]
3 [1]
4 [1]
5 [1]
6 [1, 3, 4]
7 [1]
8 [1]
9 [1]
10 [1, 5, 6]
11 [1]
12 [1, 4, 9]
13 [1]
14 [1, 7, 8]
15 [1, 6, 10]
16 [1]
17 [1]
18 [1, 9, 10]
19 [1]
20 [1, 5, 16]
21 [1, 7, 15]
22 [1, 11, 12]
23 [1]
24 [1, 9, 16]
25 [1]
26 [1, 13, 14]
27 [1]
28 [1, 8, 21]
29 [1]
30 [1, 6, 10, 15, 16, 21, 25]
31 [1]
32 [1]
33 [1, 12, 22]
34 [1, 17, 18]
35 [1, 15, 21]
36 [1, 9, 28]
37 [1]
38 [1, 19, 20]
39 [1, 13, 27]
40 [1, 16, 25]
41 [1]
42 [1, 7, 15, 21, 22, 28, 36]
43 [1]
44 [1, 12, 33]
45 [1, 10, 36]
46 [1, 23, 24]
47 [1]
48 [1, 16, 33]
49 [1]
50 [1, 25, 26]
51 [1, 18, 34]
52 [1, 13, 40]
53 [1]
54 [1, 27, 28]
55 [1, 11, 45]
56 [1, 8, 49]
57 [1, 19, 39]
58 [1, 29, 30]
59 [1]
60 [1, 16, 21, 25, 36, 40, 45]
61 [1]
62 [1, 31, 32]
63 [1, 28, 36]
64 [1]
65 [1, 26, 40]
66 [1, 12, 22, 33, 34, 45, 55]
67 [1]
68 [1, 17, 52]
69 [1, 24, 46]
70 [1, 15, 21, 35, 36, 50, 56]
71 [1]
72 [1, 9, 64]
73 [1]
74 [1, 37, 38]
75 [1, 25, 51]
76 [1, 20, 57]
77 [1, 22, 56]
78 [1, 13, 27, 39, 40, 52, 66]
79 [1]
80 [[...]<jupyter_text>We observe that $n$ has $2^t-2$ values of $a$, where $t$ is the number of prime factors of $n$:<jupyter_code>N = 50
for i in range(1, N):
    print(i, len(primeFactors(i, primes)), len(all_idempotents(i)))<jupyter_output>1 0 0
2 1 1
3 1 1
4 1 1
5 1 1
6 2 3
7 1 1
8 1 1
9 1 1
10 2 3
11 1 1
12 2 3
13 1 1
14 2 3
15 2 3
16 1 1
17 1 1
18 2 3
19 1 1
20 2 3
21 2 3
22 2 3
23 1 1
24 2 3
25 1 1
26 2 3
27 1 1
28 2 3
29 1 1
30 3 7
31 1 1
32 1 1
33 2 3
34 2 3
35 2 3
36 2 3
37 1 1
38 2 3
39 2 3
40 2 3
41 1 1
42 3 7
43 1 1
44 2 3
45 2 3
46 2 3
47 1 1
48 2 3
49 1 1<jupyter_text>Bounds for $N$ given $a$Given $a$, it appears $N\leq a(a-1)$.<jupyter_code>N = 500
a_target = 15
print(a_target, a_target*(a_target-1))
for i in range(1, N):
    all_a = all_idempotents(i)
    if a_target in all_a:
        print(i, all_a)<jupyter_output>15 210
21 [1, 7, 15]
30 [1, 6, 10, 15, 16, 21, 25]
35 [1, 15, 21]
42 [1, 7, 15, 21, 22, 28, 36]
70 [1, 15, 21, 35, 36, 50, 56]
105 [1, 15, 21, 36, 70, 85, 91]
210 [1, 15, 21, 36, 70, 85, 91, 105, 106, 120, 126, 141, 175, 190, 196]<jupyter_text>Primal Divisor Propertyif $c|ab$, then there exists $c_1, c_2$ such that $c_1|a$, $c_2|b$, $c_1c_2=c$.So for this problem,if $c|a(a-1)$, then there exists $c_1, c_2$ such that $c_1|a$, $c_2|(a-1)$, $c_1c_2=c$. AND $c_1$ and $c_2$ share NO factors ($gcf(c_1, c_2) = 1$)  Which values of $N$ have $a$ as an idempotent?It appears there are $n_f/2 -1$ values of $N$ with $a$ as an idempotent, where $n_f$ is the number of factors of $a(a-1)$.<jupyter_code>N = 4000
a_target = 11
print(a_target, a_target*(a_target-1))

idempotents = []
for i in range(1, N):
    all_a = all_idempotents(i)
    if a_target in all_a:
        idempotents.append(i)

print(f'number of factors of {a_target*(a_target-1)}:', len(factors(a_target*(a_target-1))))
print(f'number of values of N: {len(idempotents)}')<jupyter_output>11 110
number of factors of 110: 8
number of values of N: 3<jupyter_text>which values of $N$ have $a$ as the LARGEST idempotent?There are NO $N$ such that $a_{max}$ is prime.<jupyter_code>a_target = 17
print(primeFactors(a_target, primes))
N = a_target*(a_target-1) + 1

for i in range(2, N):
    all_a = all_idempotents(i)
    if a_target == max(all_a):
        print(i, max(all_a), all_a)<jupyter_output>{17: 1}<jupyter_text>If $a$ is even, then SOMETIMES $a=a_{max}$ for $N=2(a-1)$<jupyter_code>for a in range(2, 50):
    N = a*(a-1) + 1
    
    for i in range(2, N):
        all_a = all_idempotents(i)
        if all_a == [1, a-1, a]:
            print(i, all_a, (a-1)*2)
for a in range(2, 20):
    N = a*(a-1) + 1
    
    for i in range(2, N):
        all_a = all_idempotents(i)
        if a == max(all_a):
            print(a, i, all_a)
from itertools import product

N = int(1e7)

a_max = [1]*(N+1)
fact_b = [1]
for a in range(N):
    if is_prime(a):
        fact_b = [1, a]
        continue
   
    if a%100000 == 0:
        print(a)
       
    fact_a = factors(a)
    fact_ab = [_a*b for _a, b in product(fact_a, fact_b)]
    n_candid = [_n for _n in fact_ab if _n > a and _n < N+1]
   
    for n in n_candid:
        a_max[n] = max(a_max[n], a)
    fact_b = fact_a

a_max[:2] = [0, 0]
print(sum(a_max))
for i, a in enumerate(a_max):
    print(i, a)<jupyter_output>0 1
1 1
2 1
3 1
4 1
5 1
6 4
7 1
8 1
9 1
10 6
11 1
12 9
13 1
14 8
15 10
16 1
17 1
18 10
19 1
20 16
21 15
22 12
23 1
24 16
25 1
26 14
27 1
28 21
29 1
30 25
31 1
32 1
33 22
34 18
35 21
36 28
37 1
38 20
39 27
40 25
41 1
42 36
43 1
44 33
45 36
46 24
47 1
48 33
49 1
50 26
51 34
52 40
53 1
54 28
55 45
56 49
57 39
58 30
59 1
60 45
61 1
62 32
63 36
64 1
65 40
66 55
67 1
68 52
69 46
70 56
71 1
72 64
73 1
74 38
75 51
76 57
77 56
78 66
79 1
80 65
81 1
82 42
83 1
84 64
85 51
86 44
87 58
88 56
89 1
90 81
91 78
92 69
93 63
94 48
95 76
96 64
97 1
98 50
99 55
100 1
{'fraction_non_alphanumeric': 0.15709489309065205, 'fraction_numerical': 0.21858985686517052, 'mean_word_length': 2.834688346883469, 'pattern_counts': {'":': 0, '<': 22, '<?xml version=': 0, '>': 20, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 11, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '6', 'dir': 'jupyter-structured-clean-dedup', 'id': '542883', 'license': 'MIT', 'n_tokens_mistral': 3635, 'n_tokens_neox': 2763, 'n_words': 1125, 'path': 'Python/407.ipynb', 'repo_name': 'jaimeliew1/Project_Euler_Solutions', 'size': '5659'}