|
%I #18 May 16 2013 14:13:06
%S 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,
%T 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,
%U 11,2,0,8,5,18,5,20,3,26,1,72,13,10,15
%N Smallest remainder of p+q modulo n, where p*q = n^2 - 1, 1 < p < n-1, or n if no such factorization exists.
%C 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.
%H Charles R Greathouse IV, <a href="/A069817/b069817.txt">Table of n, a(n) for n = 1..10000</a>
%H Art of Problem Solving, <a href="http://www.artofproblemsolving.com/Wiki/index.php/1988_IMO_Problems/Problem_6">1988 IMO Problems/Problem 6</a>
%F 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.
%e 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.
%t 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 *)
%o (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
%o (Haskell)
%o a069817 1 = 1
%o a069817 n = if null ms then n else minimum $ map (`mod` n) ms
%o where ms = zipWith (+) ds $ map (div n') ds
%o ds = takeWhile (< n - 1) $ tail $ a027750_row n'
%o n' = n ^ 2 - 1
%o -- _Reinhard Zumkeller_, May 16 2013
%Y Cf. A027750, A005563.
%K easy,nice,nonn
%O 1,2
%A _Rainer Rosenthal_, Apr 29 2002
%E a(17)-a(75) from _Charles R Greathouse IV_, Apr 04 2013
|
