A366330 -id:A366330 - cp's OEIS frontend

A366219 Smallest positive integer whose smallest coprime divisor shift is n.

1, 3, 91, 325, 2093, 1001, 12025, 1045, 4945, 6391, 189, 455, 245, 11825, 128843, 368809, 273, 1295, 14495, 37961, 252263, 91375, 595, 13013, 46189, 104951, 63875, 136345, 42237, 22253, 192647, 18655, 8225, 194545, 200629, 192907, 27625, 1911, 464783, 27797

Offset: 0

M. Farrokhi D. G., Oct 05 2023

nonn

A nonnegative number s is a coprime divisor shift of n if GCD(d + s, n) = 1 for all divisors d of n. The coprime divisor shift of n is the infimum of the set of all nonnegative coprime divisor shifts of n.

Conjecture. Every positive integer s is the coprime divisor shift of a positive integer.

			a(0) = 1 for GCD(1 + 0, 1) = 1.
a(1) = 3 for GCD(1 + 1, 3) = GCD(3 + 1, 3) = 1 but GCD(1 + 1, 2) > 1.
a(2) = 91 for GCD(d + 2, 91) = 1 for all divisors d = 1, 7, 13, 91 of 91, GCD(13 + 1, 91) > 1, and 91 is the smallest number with this property.

M. Farrokhi D. G., Table of n, a(n) for n = 0..1000

Cf. A366251, A366330.

isds(k,s)={fordiv(k,d,if(gcd(d+s, k)<>1, return(0))); 1}
findds(k)={for(s=0, k-1, if(isds(k,s), return(s))); -1}
a(n)={for(k=1, oo, if(isds(k,n) && findds(k)==n, return(k)))} \\ Andrew Howroyd, Oct 05 2023

A366251 Numbers with a coprime divisor shift.

Original entry on oeis.org

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

Offset: 1

M. Farrokhi D. G., Oct 05 2023

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.
From David A. Corneth, Oct 06 2023: (Start)
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)

			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.

M. Farrokhi D. G., Table of n, a(n) for n = 1..10000

Cf. A366219, A366330.

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;

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:
aList(133);  # Peter Luschny, Oct 06 2023
# More efficient, after David A. Corneth:
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)]):
aList(145);  # Peter Luschny, Oct 07 2023

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];
aList[145] (* Jean-François Alcover, Oct 27 2023, after Peter Luschny *)

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}
select(k->findds(k), [1..150]) \\ Andrew Howroyd, Oct 05 2023

is(n) = {
	if(!bitand(n, 1), return(0));
	my(d = divisors(n));
	forprime(p = 3, #d,
		if(#Set(d % p) == p,
			return(0)
		)
	); 1	
} \\ David A. Corneth, Oct 06 2023

cp's OEIS Frontend

A366219 Smallest positive integer whose smallest coprime divisor shift is n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

A366251 Numbers with a coprime divisor shift.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

GAP

Maple

Mathematica

PARI

PARI