cp's OEIS Frontend

A182665 Greatest x < n such that n divides x*(x-1).

%I A182665 #40 Jan 20 2025 18:41:28
%S A182665 0,1,1,1,1,4,1,1,1,6,1,9,1,8,10,1,1,10,1,16,15,12,1,16,1,14,1,21,1,25,
%T A182665 1,1,22,18,21,28,1,20,27,25,1,36,1,33,36,24,1,33,1,26,34,40,1,28,45,
%U A182665 49,39,30,1,45,1,32,36,1,40,55,1,52,46,56,1,64,1,38,51,57,56,66,1,65,1,42,1,64,51,44,58,56,1,81,78,69,63,48,76,64,1,50,55
%N A182665 Greatest x < n such that n divides x*(x-1).
%C A182665 a(n) = 1 iff n is in A246655. - _Robert Israel_, Jan 13 2015
%H A182665 Robert Israel, <a href="/A182665/b182665.txt">Table of n, a(n) for n = 1..10000</a>
%H A182665 <a href="http://math.stackexchange.com/questions/264290/division-into-xx-1/264307#264307">Question on math.stackexchange.com</a>
%F A182665 a(n) = n - A344005(n). - _Antti Karttunen_, May 19 2022
%e A182665 a(6) = 4 because 6 divides 4*3=12 but does not divide 5*4=20.
%p A182665 A:= proc(n)
%p A182665        max(map(u -> u*modp(1/u,n/u),
%p A182665                       map(t -> mul(s[1]^s[2],s = t),
%p A182665                           combinat[powerset](ifactors(n)[2]))))
%p A182665      end proc;
%p A182665 seq(A(n),n=1..100);
%t A182665 a[n_] := Module[{x}, Max[x /. {ToRules[Reduce[Mod[x*(x-1), n] == 0 && Mod[x*(x+1), n] != 0, x, Integers] /. C[_] -> 0]}]]; a[1] = 0; a[2] = 1; Table[a[n], {n, 1, 100}] (* _Jean-François Alcover_, Mar 04 2014 *)
%o A182665 (PARI) A182665(n) = forstep(x=n-1,0,-1,if(!((x*(x-1))%n),return(x))); \\ _Antti Karttunen_, Jun 12 2022
%o A182665 (Python)
%o A182665 from itertools import combinations
%o A182665 from math import prod
%o A182665 from sympy import factorint
%o A182665 from sympy.ntheory.modular import crt
%o A182665 def A182665(n):
%o A182665     if n == 1:
%o A182665         return 0
%o A182665     plist = tuple(p**q for p, q in factorint(n).items())
%o A182665     return 1 if len(plist) == 1 else n-int(min(min(crt((m, n//m), (0, -1))[0], crt((n//m, m), (0, -1))[0]) for m in (prod(d) for l in range(1, len(plist)//2+1) for d in combinations(plist, l)))) # _Chai Wah Wu_, Jun 12 2022
%Y A182665 Cf. A246655, A345992 [= gcd(a(n), n) = gcd(a(n), A344005(n))], A354919, A354920 (parity), A354921 (positions of odd terms), A354922 (of even terms).
%K A182665 nonn,easy
%O A182665 1,6
%A A182665 _Robert Israel_, Dec 23 2012