login
Constant c(p) used in determining divisibility by the n-th prime, p=A000040(n), for n>=4.
3

%I #32 Jun 26 2023 10:18:04

%S -2,-1,4,-5,2,7,3,-3,-11,-4,13,-14,16,6,-6,-20,-7,22,8,25,9,-29,-10,

%T 31,-32,11,34,-38,-13,-41,14,15,-15,-47,49,-50,52,18,-18,-19,58,-59,

%U 20,-21,67,-68,23,70,24,-24,-25,-77,79,27,-27,-83,-28,85,88,-92,-31,94,-95,-33,-101,-104,35,106,36,-110,112,38

%N Constant c(p) used in determining divisibility by the n-th prime, p=A000040(n), for n>=4.

%C To determine if N is divisible by p: Write N=10*M+D, where D=ones digit of N and M=N without ones digit. Then N is divisible by p iff M+c(p)*D is.

%C c(p) is the multiplicative inverse of 10 (mod p) with the smallest absolute value. (But note that the link below uses c(13)=9 rather than -4.)

%C For a given n, a(n) is either -A103876(n) or prime(n)-A103876(n), whichever has a smaller absolute value. - _Nicholas Stefan Georgescu_, Jan 18 2023

%H Ethan Magness, Steven Sinnott and Robert L. Ward, <a href="https://web.archive.org/web/20180312073749/http://mathforum.org/k12/mathtips/division.tips.html">Divisibility Rules</a>

%e The first few terms are c(7)=-2, c(11)=-1, c(13)=4. To find out if a number is divisible by 7, take the last digit, double it and subtract the result from the rest of the number. If you get an answer divisible by 7 (including 0), then the original number is divisible by 7. If you do not know the new number's divisibility, you can apply the rule again. Example: If you had 203, you would subtract 2*3=6 from 20 to get 14; since 14 is divisible by 7, so is 203.

%t c[p_] := If[(v=PowerMod[10, -1, p])>p/2, v-p, v]; c/@Prime/@Range[4, 100]

%o (Python)

%o import sympy

%o [(pow(10, -1, p))-p*(p%10%6==1) for p in sympy.primerange(7, 300)]

%o # _Nicholas Stefan Georgescu_, Jan 18 2023

%o (PARI) a(n) = centerlift(Mod(1,prime(n))/10); \\ _Kevin Ryde_, Feb 18 2023

%Y Cf. A103876, A357913.

%K sign,base

%O 4,1

%A Devora Rahav (rahav-d(AT)inter.net.il), Dec 09 2002

%E Edited by _Dean Hickerson_, Dec 23 2002