cp's OEIS Frontend

A355269 Lexicographically earliest infinite sequence of distinct positive integers such that a(n+1) is prime to the number of divisors of a(n).

%I A355269 #33 Jul 01 2025 23:33:51
%S A355269 1,2,3,5,7,9,4,8,11,13,15,17,19,21,23,25,10,27,29,31,33,35,37,39,41,
%T A355269 43,45,47,49,14,51,53,55,57,59,61,63,65,67,69,71,73,75,77,79,81,6,83,
%U A355269 85,87,89,91,93,95,97,99,101,103,105,107,109,111,113,115,117,119
%N A355269 Lexicographically earliest infinite sequence of distinct positive integers such that a(n+1) is prime to the number of divisors of a(n).
%C A355269 1,2,3 are the earliest consecutive numbers satisfying the definition, therefore these are the initial terms. The sequence is infinite since there is always a number prime to d(a(n)), and we take the least such as a(n+1).
%C A355269 Tau(k) is odd iff k is a square, therefore if a(n) is nonsquare, a(n+1) is odd. Consequently the sequence displays runs of consecutive odd nonsquare numbers, extending between successive odd squares, whereupon the parity of tau(a(n)) changes from even to odd. While odd numbers occur early, even numbers are very delayed because (in general) an even number can only be admitted following an odd square, or (on rarer occasions) following an even square subsequent to an odd square (the only time we observe two consecutive even terms).
%C A355269 Conjectures: When a(n) is square a(n+1) is even; no two squares of equal parity can appear as adjacent terms; sequence is a permutation of the positive integers with primes in natural order.
%C A355269 From _Michael De Vlieger_, Jun 28 2022: (Start)
%C A355269 Let j = a(n-1), k = a(n), tau(m) = A000005(m), and P(m) = A002110(m).
%C A355269 Theorem: prime p | tau(j) implies gcd(p, k) = 1. Consequence of sequence definition.
%C A355269 Even tau(j) implies nonsquare j (in A000037), which in turn implies odd k. Prime j implies tau(j) = 2, which in turn implies odd k. Therefore there is a significant tendency for k to be odd.
%C A355269 Square j (in A000290) implies odd tau(j) but do not necessarily lead to even k. For n > 3, the smallest missing numbers are even, therefore even k is likely to enter the sequence following square j.
%C A355269 Terms j such that tau(j) is coprime to 6, i.e., j in A352475, allow successor k such that 6 | k. For n > 7, the smallest missing number is divisible by 6 because we usually have gcd(tau(j), 6) > 1. Therefore k such that 6 | k likely follows j such that tau(j) is coprime to 6. A similar argument can be made regarding j such that tau(j) is coprime to 30, i.e., j in A354178.
%C A355269 Primorials appear latest in this sequence because they are divisible by the smallest primes. For example, a(1132) = 30 and a(4884401) = 210.
%C A355269 Generally, we have k : k | P(m) iff j : (tau(j), P(m)) = 1. Since gcd(tau(j), P(m)) > 1 is more common than gcd(tau(j), P(m)) = 1 for m > 1, we are apt to see k | P(m). (End)
%H A355269 Michael De Vlieger, <a href="/A355269/b355269.txt">Table of n, a(n) for n = 1..10000</a>
%H A355269 Michael De Vlieger, <a href="/A355269/a355269.png">Annotated log log scatterplot of a(n)</a>, n = 1..2^16, showing records in red and local minima in blue. Three prominent trajectories appear; that of odd and early terms mostly in red, that of terms divisible by 6 mostly in blue, and even numbers that are not divisible by 6 in green. (It may be that numbers divisible by 6 are not always minima; instead, numbers divisible by a larger primorial may be delayed to a greater degree than those merely divisible by 6 for large n.)
%e A355269 a(4)=5 because a(3)=3 has 2 divisors and 5 is the least unused term prime to 2. Likewise a(5) = 7, and a(6) = 9, the first odd square. Since 9 has 3 divisors a(7) is 4, the smallest unused number prime to 3, and the first occurrence of an even square, also having 3 divisors. Consequently a(8)=8, the smallest unused number prime to 3. Thus we see 4,8 the first occasion of a pair of adjacent even terms, consequence of odd square (9) followed by even square (4). The next occasion is a(67,68,69)=121,16,12.
%t A355269 Block[{a, c, j, k, u, v, nn}, nn = 120; a[1] = c[1] = j = 1; u = 2; v = 3; Do[k = u; If[EvenQ[j], k = v; While[Nand[c[k] == 0, CoprimeQ[j, k]], k += 2], While[Nand[c[k] == 0, CoprimeQ[j, k]], k++]]; Set[{a[i], c[k]}, {k, i}]; j = DivisorSigma[0, k]; If[k == u, While[c[u] != 0, u++]]; If[k == v, While[c[v] != 0, v += 2]], {i, 2, nn}]; Array[a, nn] ] (* _Michael De Vlieger_, Jun 28 2022 *)
%o A355269 (Python)
%o A355269 from math import gcd
%o A355269 from sympy import divisor_count
%o A355269 from itertools import count, islice
%o A355269 def agen(): # generator of terms
%o A355269     aset, k, mink = {1, 2}, 1, 3; yield from [1, 2]
%o A355269     for n in count(3):
%o A355269         an, k = k, mink
%o A355269         while k in aset or not gcd(divisor_count(an), k) == 1: k += 1
%o A355269         aset.add(k); yield k
%o A355269         while mink in aset: mink += 1
%o A355269 print(list(islice(agen(), 66))) # _Michael S. Branicky_, Jun 28 2022
%Y A355269 Cf. A000005, A000037, A000290, A002110, A352475, A354178, A354903, A016742, A016754.
%K A355269 nonn
%O A355269 1,2
%A A355269 _David James Sycamore_ and _Michael De Vlieger_, Jun 26 2022