A368110 Numbers of which it is possible to choose a different divisor of each prime index.

1, 2, 3, 5, 6, 7, 9, 10, 11, 13, 14, 15, 17, 19, 21, 22, 23, 25, 26, 29, 30, 31, 33, 34, 35, 37, 38, 39, 41, 42, 43, 45, 46, 47, 49, 51, 53, 55, 57, 58, 59, 61, 62, 63, 65, 66, 67, 69, 70, 71, 73, 74, 75, 77, 78, 79, 82, 83, 85, 86, 87, 89, 91, 93, 94, 95, 97

Offset

1,2

Comments

A prime index of n is a number m such that prime(m) divides n. The multiset of prime indices of n is row n of A112798.

By Hall's marriage theorem, k is a term if and only if there is no sub-multiset S of the prime indices of k such that fewer than |S| numbers are divisors of a member of S. Equivalently, there is no divisor of k in A370348. - Robert Israel, Feb 15 2024

Links

Robert Israel, Table of n, a(n) for n = 1..10000

Formula

Heinz numbers of the partitions counted by A239312.

Example

The terms together with their prime indices begin:
   1: {}
   2: {1}
   3: {2}
   5: {3}
   6: {1,2}
   7: {4}
   9: {2,2}
  10: {1,3}
  11: {5}
  13: {6}
  14: {1,4}
  15: {2,3}
  17: {7}
  19: {8}
  21: {2,4}
  22: {1,5}
  23: {9}
  25: {3,3}
  26: {1,6}
  29: {10}
  30: {1,2,3}

Maple

filter:= proc(n) uses numtheory, GraphTheory; local B, S, F, D, E, G, t, d;
  F:= ifactors(n)[2];
  F:= map(t -> [pi(t[1]), t[2]], F);
  D:= `union`(seq(divisors(t[1]), t = F));
  F:= map(proc(t) local i; seq([t[1], i], i=1..t[2]) end proc, F);
  if nops(D) < nops(F) then return false fi;
  E:= {seq(seq({t, d}, d=divisors(t[1])), t = F)};
  S:= map(t -> convert(t, name), [op(F), op(D)]);
  E:= map(e -> map(convert, e, name), E);
  G:= Graph(S, E);
  B:= BipartiteMatching(G);
  B[1] = nops(F);
end proc:
select(filter, [$1..100]); # Robert Israel, Feb 15 2024

Mathematica

prix[n_]:=If[n==1, {}, Flatten[Cases[FactorInteger[n], {p_, k_}:>Table[PrimePi[p], {k}]]]];
Select[Range[100], Select[Tuples[Divisors/@prix[#]], UnsameQ@@#&]!={}&]

Crossrefs

Partitions of this type are counted by A239312, complement A370320.

Positions of nonzero terms in A355739.

Complement of A355740.

For just prime divisors we have A368100, complement A355529 (odd A355535).

A000005 counts divisors.

A003963 multiplies together the prime indices of n.

A056239 adds up prime indices, row sums of A112798, counted by A001222.

A120383 lists numbers divisible by all of their prime indices.

A324850 lists numbers divisible by the product of their prime indices.

A355731 counts choices of a divisor of each prime index, firsts A355732.

A355741 chooses prime factors of prime indices, variations A355744, A355745.

Cf. A000720, A076610, A111774, A335433, A335448, A340852, A355733, A355734, A355737, A355749, A370348.

Sequence in context: A370422 A371170 A371088 * A083347 A137217 A367625

Adjacent sequences: A368107 A368108 A368109 * A368111 A368112 A368113

Keyword

nonn

Author

Gus Wiseman, Dec 15 2023

Status

approved