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,1

Links

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

Example

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.

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

Prog

(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

Crossrefs

Second column of A113031.

Sequence in context: A338712 A263926 A114788 * A175637 A110404 A366529

Adjacent sequences: A085071 A085072 A085073 * A085075 A085076 A085077

Keyword

nonn

Author

Amarnath Murthy, Jul 01 2003

Extensions

More terms from David Wasserman, Jan 12 2005

Status

approved