|
| |
|
|
A366251
|
|
Numbers with a coprime divisor shift.
|
|
3
|
|
|
|
1, 3, 5, 7, 9, 11, 13, 17, 19, 21, 23, 25, 27, 29, 31, 35, 37, 39, 41, 43, 47, 49, 53, 55, 57, 59, 61, 63, 65, 67, 71, 73, 77, 79, 81, 83, 85, 89, 91, 93, 95, 97, 101, 103, 107, 109, 111, 113, 115, 117, 119, 121, 125, 127, 129, 131, 133, 137, 139, 143, 145
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,2
|
|
|
COMMENTS
|
A number k has a coprime divisor shift s if GCD(d + s, k) = 1 for all divisors d of k.
If k is in the sequence, then all divisors of k are in the sequence too.
As a consequence of the above, if some m is not in the sequence then any multiple of m is not in the sequence either. So all terms are odd as 2 is not in the sequence.
To see if k is a term we can do the following:
- Check whether k is even; if so then k is not in the sequence.
- Make a list of the divisors of k. Let tau(k) be the number of divisors of k. Then for each prime p <= tau(k) if the number of residues mod p of the divisors of k is equal to p then k is not in the sequence. Otherwise by the Chinese Remainder Theorem we can find a number s such that gcd(d + s, n) = 1 for all d.
So every odd prime is a term. (End)
|
|
|
LINKS
|
|
|
|
EXAMPLE
|
1 is a term since GCD(1 + 0, 1) = 1.
2 is not a term since GCD(1 + s, 2) > 1 or GCD(2 + s, 2) > 1 for all nonnegative integers s.
3 is a term since GCD(1 + 1, 3) = GCD(3 + 1, 3) = 1.
|
|
|
MAPLE
|
aList := proc(len) local isds, findds;
isds := (k, s) -> andmap(d -> igcd(d + s, k) = 1, NumberTheory:-Divisors(k));
findds := k -> ormap(s -> isds(k, s), [seq(1..k)]);
select(k -> findds(k), [seq(1..len)]) end:
isa := proc(n) local d, p, t; p := 3;
if irem(n, 2) = 0 then return false fi;
d := NumberTheory:-Divisors(n);
while p < nops(d) do
{seq(irem(t, p), t = d)};
if nops(%) = p then return false fi;
p := nextprime(p);
od: true end:
aList := len -> select(isa, [seq(1..len)]):
|
|
|
MATHEMATICA
|
isa[n_] := Module[{d, p, t}, p = 3; If[Mod[n, 2] == 0, Return[False]]; d = Divisors[n]; While[p < Length[d], If[Length[Union@Table[Mod[t, p], {t, d}]] == p, Return[False]]; p = NextPrime[p]]; True];
aList[len_] := Select[Range[len], isa];
|
|
|
PROG
|
(PARI)
isds(k, s)={fordiv(k, d, if(gcd(d+s, k)<>1, return(0))); 1}
findds(k)={for(s=1, k, if(isds(k, s), return(s))); 0}
(PARI)
is(n) = {
if(!bitand(n, 1), return(0));
my(d = divisors(n));
forprime(p = 3, #d,
if(#Set(d % p) == p,
return(0)
)
); 1
(GAP)
CoprimeDivisorShift := function(n)
local shift, divisors;
shift := 0;
if not IsPrimeInt(n) and First(PrimeDivisors(n), p -> CoprimeDivisorShift(n / p) = infinity) <> fail then
shift := infinity;
fi;
if shift < infinity then
divisors := DivisorsInt(n);
while shift < n and First(divisors, d -> GcdInt(d + shift, n) > 1) <> fail do
shift := shift + 1;
od;
if shift = n then
shift := infinity;
fi;
fi;
return shift;
end;
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,easy
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
