login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

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
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
Charles R Greathouse IV, Table of n, a(n) for n = 1..10000
Art of Problem Solving, 1988 IMO Problems/Problem 6
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
-- Reinhard Zumkeller, May 16 2013
CROSSREFS
Sequence in context: A066262 A195989 A174715 * A071439 A100941 A082119
KEYWORD
easy,nice,nonn
AUTHOR
Rainer Rosenthal, Apr 29 2002
EXTENSIONS
a(17)-a(75) from Charles R Greathouse IV, Apr 04 2013
STATUS
approved