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

3, 7, 9, 11, 55, 29, 4913, 289, 21, 23, 325, 53, 15, 46, 81, 103, 325, 191, 261, 22, 111, 47, 3625, 10201, 183, 6859, 477, 59, 1771, 311, 8587340257, 34, 35, 106, 1225, 149, 39, 118, 1161, 83, 715, 173, 45, 316, 93, 283, 60625, 9409, 801, 205, 261, 107, 11125

Offset: 2

Author

Amarnath Murthy, Jul 01 2003

Keywords

• nonn

Examples

			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.
		

Links

• Robert Israel, Table of n, a(n) for n = 2..719

Crossrefs

Second column of A113031.

Programs

Maple

f:= proc(n) local k, s, p, best, q, r, x;
  s:= ps(n);
  if nops(s) = 1 then
     s:= s[1]; p:= 1; do p:= nextprime(p); if p^s mod n = 1 then return p^s fi od
  elif nops(s) = 2 then
    p:= 1; best:= infinity;
    do
      p:=nextprime(p);
      if n mod p = 0 then next fi;
      if 2^s[1]*p^s[2] > best then return best fi;
      if [msolve(x^s[1]*p^s[2]=1, n)]=[] then next fi;
      q:= 1;
      do
        q:= nextprime(q);
        if q = p or n mod q = 0 then next fi;
        r:= q^s[1]*p^s[2];
        if r > best then break fi;
        if r mod n = 1 then best:= r fi;
      od
    od
  fi;
  for k from 1 by n do if ps(k) = s then return k fi od
end proc:
map(f, [$1..100]); # Robert Israel, Mar 23 2021

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

Extensions

More terms from David Wasserman, Jan 12 2005