login
Number of extradivisors of n (m < n is an extradivisor of n if for some positive k < n, m | n | k^(n+1) + m and n | (n-k)^(n+1) + m).
6

%I #54 Jun 29 2024 16:44:22

%S 0,1,0,0,1,1,0,0,0,1,0,0,1,1,1,0,1,1,0,0,1,1,0,0,1,1,0,0,1,1,0,0,1,1,

%T 0,0,1,1,0,0,1,1,0,0,2,1,0,0,0,1,1,0,1,1,0,0,1,1,0,0,1,1,0,0,1,1,0,0,

%U 1,1,0,0,1,1,0,0,1,1,0,0,0,1,0,0,1,1,1,0,1,1

%N Number of extradivisors of n (m < n is an extradivisor of n if for some positive k < n, m | n | k^(n+1) + m and n | (n-k)^(n+1) + m).

%C All extradivisors of n are odd numbers.

%C Extradivisor primes (even prime 2 and Pythagorean primes (A002144) base extradivisor 1): 2, 5, 13, 17, 29, 37, 53, 61, 137, 181, 229, 233, 257, 281, 353, 373, 421, 433, 449, 457, 557, 641, 653, 709, 733, 773, 809, 877, 941, 1021, ...

%C Extradivisor semiprimes: 6, 10, 14, 15, 21, 22, 25, 26, 33, 34, 38, 46, 51, 57, 58, 62, 65, 69, 74, 77, 82, 85, 86, 87, ...

%C From _Michael De Vlieger_, Dec 07 2016: (Start)

%C Smallest number with n extradivisors: {1, 2, 45, 105, 1365, 1305, ...}.

%C a(n) = 0 for n == 0 (mod 4) in observed cases with n <= 3000. (End)

%H Michael De Vlieger, <a href="/A279024/b279024.txt">Table of n, a(n) for n = 1..10000</a>

%e 1 is an extradivisor of 2 because 2 divides 1^(2+1) + 1 and (2-1)^(2+1) + 1; 2 divides 2 and 2.

%e 1 is an extradivisor of 5 because 5 divides 2^(5+1) + 1 and (5-2)^(5+1) + 1; 5 divides 65 and 730.

%e 3 is an extradivisor of 6 because 6 divides 3^(6+1) + 3 and (6-3)^(6+1) + 3; 6 divides 2190 and 2190.

%t Table[Length@ Select[DeleteCases[Most@ Divisors@ n, d_ /; EvenQ@ d], Function[m, AnyTrue[Range[n - 1], Function[k, And[Divisible[k^(n + 1) + m, n], Divisible[(n - k)^(n + 1) + m, n]]]]]], {n, 90}] (* Version 10, eliminate "Length@" to list extradivisors, or *)

%t Table[Count[Select[Most@ Divisors@ n, OddQ], _?(Total@ Boole@ Map[Function[k, And[Mod[k^(n + 1) + #, n] == 0, Mod[(n - k)^(n + 1) + #, n] == 0]], Range[1, n - 1, 2]] > 0 &)], {n, 3*10^3}] (* _Michael De Vlieger_, Dec 07 2016, more efficient Jun 17 2020 *)

%Y Cf. A000005, A002144, A027750, A278921, A279680.

%K nonn

%O 1,45

%A _Juri-Stepan Gerasimov_, Dec 03 2016

%E a(42) and a(60) corrected by _Jon E. Schoenfield_, Dec 03 2016

%E Definition edited by _N. J. A. Sloane_, Jun 19 2020