cp's OEIS Frontend

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

%I A355740 #15 Feb 16 2024 09:56:59
%S A355740 4,8,12,16,18,20,24,27,28,32,36,40,44,48,50,52,54,56,60,64,68,72,76,
%T A355740 80,81,84,88,90,92,96,100,104,108,112,116,120,124,125,126,128,132,135,
%U A355740 136,140,144,148,150,152,156,160,162,164,168,172,176,180,184,188
%N A355740 Numbers of which it is not possible to choose a different divisor of each prime index.
%C A355740 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.
%C A355740 By Hall's marriage theorem, k is a term if and only if there is a sub-multiset S of the prime indices of k such that fewer than |S| numbers are divisors of a member of S. Equivalently, k is divisible by a member of A370348. - _Robert Israel_, Feb 15 2024
%H A355740 Robert Israel, <a href="/A355740/b355740.txt">Table of n, a(n) for n = 1..10000</a>
%H A355740 Wikipedia, <a href="https://en.wikipedia.org/wiki/Cartesian_product">Cartesian product</a>.
%F A355740 We have A001221(a(n)) >= A303975(a(n)).
%e A355740 The terms together with their prime indices begin:
%e A355740     4: {1,1}
%e A355740     8: {1,1,1}
%e A355740    12: {1,1,2}
%e A355740    16: {1,1,1,1}
%e A355740    18: {1,2,2}
%e A355740    20: {1,1,3}
%e A355740    24: {1,1,1,2}
%e A355740    27: {2,2,2}
%e A355740    28: {1,1,4}
%e A355740    32: {1,1,1,1,1}
%e A355740    36: {1,1,2,2}
%e A355740    40: {1,1,1,3}
%e A355740    44: {1,1,5}
%e A355740    48: {1,1,1,1,2}
%e A355740 For example, the choices of a divisor of each prime index of 90 are: (1,1,1,1), (1,1,1,3), (1,1,2,1), (1,1,2,3), (1,2,1,1), (1,2,1,3), (1,2,2,1), (1,2,2,3). But none of these has all distinct elements, so 90 is in the sequence.
%p A355740 filter:= proc(n) uses numtheory, GraphTheory; local B, S, F, D, E, G, t, d;
%p A355740   F:= ifactors(n)[2];
%p A355740   F:= map(t -> [pi(t[1]), t[2]], F);
%p A355740   D:= `union`(seq(divisors(t[1]), t = F));
%p A355740   F:= map(proc(t) local i; seq([t[1], i], i=1..t[2]) end proc, F);
%p A355740   if nops(D) < nops(F) then return false fi;
%p A355740   E:= {seq(seq({t, d}, d=divisors(t[1])), t = F)};
%p A355740   S:= map(t -> convert(t, name), [op(F), op(D)]);
%p A355740   E:= map(e -> map(convert, e, name), E);
%p A355740   G:= Graph(S, E);
%p A355740   B:= BipartiteMatching(G);
%p A355740   B[1] = nops(F);
%p A355740 end proc:
%p A355740 remove(filter, [$1..200]); # _Robert Israel_, Feb 15 2024
%t A355740 primeMS[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
%t A355740 Select[Range[100],Select[Tuples[Divisors/@primeMS[#]],UnsameQ@@#&]=={}&]
%Y A355740 Positions of 0's in A355739.
%Y A355740 The case of just prime factors (not all divisors) is A355529, odd A355535.
%Y A355740 The unordered case is counted by A355733, firsts A355734.
%Y A355740 A000005 counts divisors.
%Y A355740 A001414 adds up distinct prime divisors, counted by A001221.
%Y A355740 A003963 multiplies together the prime indices of n.
%Y A355740 A056239 adds up prime indices, row sums of A112798, counted by A001222.
%Y A355740 A120383 lists numbers divisible by all of their prime indices.
%Y A355740 A324850 lists numbers divisible by the product of their prime indices.
%Y A355740 A355731 counts choices of a divisor of each prime index, firsts A355732.
%Y A355740 A355741 chooses prime factors of prime indices, variations A355744, A355745.
%Y A355740 Cf. A000720, A076610, A335433, A335448, A340827, A355737, A355749, A370348.
%K A355740 nonn
%O A355740 1,1
%A A355740 _Gus Wiseman_, Jul 22 2022