A085074 - OEIS

%I #13 Jun 14 2022 12:13:57

%S 3,7,9,11,55,29,4913,289,21,23,325,53,15,46,81,103,325,191,261,22,111,

%T 47,3625,10201,183,6859,477,59,1771,311,8587340257,34,35,106,1225,149,

%U 39,118,1161,83,715,173,45,316,93,283,60625,9409,801,205,261,107,11125

%N Smallest number a(n) == 1 (mod n) such that the prime signature of n and a(n) is the same.

%H Robert Israel, <a href="/A085074/b085074.txt">Table of n, a(n) for n = 2..719</a>

%e a(6) = 55 = 9*6 +1 = 11*5 and 6 = 2*3 are both of prime signature p*q, where p and q are primes.

%p f:= proc(n) local k, s, p, best, q, r, x;

%p   s:= ps(n);

%p   if nops(s) = 1 then

%p      s:= s[1]; p:= 1; do p:= nextprime(p); if p^s mod n = 1 then return p^s fi od

%p   elif nops(s) = 2 then

%p     p:= 1; best:= infinity;

%p     do

%p       p:=nextprime(p);

%p       if n mod p = 0 then next fi;

%p       if 2^s[1]*p^s[2] > best then return best fi;

%p       if [msolve(x^s[1]*p^s[2]=1, n)]=[] then next fi;

%p       q:= 1;

%p       do

%p         q:= nextprime(q);

%p         if q = p or n mod q = 0 then next fi;

%p         r:= q^s[1]*p^s[2];

%p         if r > best then break fi;

%p         if r mod n = 1 then best:= r fi;

%p       od

%p     od

%p   fi;

%p   for k from 1 by n do if ps(k) = s then return k fi od

%p end proc:

%p map(f, [$1..100]); # _Robert Israel_, Mar 23 2021

%o (PARI) a(n) = my(ps = vecsort(factor(n)[, 2]), k = 1); while (vecsort(factor(k*n+1)[, 2]) != ps, k++); return (k*n+1); \\ _Michel Marcus_, Sep 15 2013; corrected Jun 14 2022

%Y Second column of A113031.

%K nonn

%O 2,1

%A _Amarnath Murthy_, Jul 01 2003

%E More terms from _David Wasserman_, Jan 12 2005