|
| |
|
|
A069817
|
|
Smallest remainder of p+q modulo n, where p*q = n^2 - 1, 1 < p < n-1, or n if no such factorization exists.
|
|
2
|
|
|
|
1, 2, 3, 4, 1, 6, 2, 0, 3, 6, 1, 12, 3, 2, 0, 8, 2, 18, 1, 4, 0, 10, 2, 0, 5, 6, 3, 12, 1, 30, 2, 8, 12, 2, 0, 12, 7, 10, 3, 16, 1, 42, 3, 4, 15, 14, 2, 0, 2, 14, 3, 20, 3, 6, 0, 0, 15, 22, 4, 60, 11, 2, 0, 8, 5, 18, 5, 20, 3, 26, 1, 72, 13, 10, 15
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,2
|
|
|
COMMENTS
|
Factoring n^2-k = p*q for k > 1 gives p+q never divisible by k*a. The remainders p+q mod k*a have minimum > 0 for k > 1. This sequence shows the minimum for k=1, where there are zero values, e.g. a(8)=0. The restriction 1 < p < n-1 is due to the fact that (n-1)(n+1) = n^2-1 and (n-1)+(n+1)=2n is zero mod n. Excluding this trivial case as well as 1*(n^2-1) with 1+(n^2-1)=n^2=0 (mod n) gives the more interesting elements.
|
|
|
LINKS
|
|
|
|
FORMULA
|
If n-1 and n+1 are prime then set a(n) = n. Otherwise check (p+q mod n) for all natural numbers p, q which satisfy: p*q = n^2-1 and 1 < p < n-1 and 1 < q < n-1.
|
|
|
EXAMPLE
|
a(7)=2 since 7^2-1 = 48 = 2*24 = 3*16 = 4*12 where the sums of the factors (mod 7) are: [2+24]=5, [3+16]=5, [4+12]=2.
|
|
|
MATHEMATICA
|
a[n_] := (r = Reduce[1 < p < n - 1 && n^2 - 1 == p*q, {p, q}, Integers]; factors = If[r === False, n, {p, q} /. {ToRules[r]}]; Mod[#[[1]] + #[[2]], n] & /@ factors // Min); Table[ a[n] , {n, 1, 16}] (* Jean-François Alcover, Apr 04 2013 *)
|
|
|
PROG
|
(PARI) a(n)=if(n<5, n, my(r=n, k=n^2-1, t); fordiv(k, p, t=(p+k/p)%n; if(t<r && p>1, if(p+1==n, return(r), r=t)))) \\ Charles R Greathouse IV, Apr 04 2013
(Haskell)
a069817 1 = 1
a069817 n = if null ms then n else minimum $ map (`mod` n) ms
where ms = zipWith (+) ds $ map (div n') ds
ds = takeWhile (< n - 1) $ tail $ a027750_row n'
n' = n ^ 2 - 1
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
easy,nice,nonn
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
