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

%I #15 Feb 16 2024 09:56:59

%S 4,8,12,16,18,20,24,27,28,32,36,40,44,48,50,52,54,56,60,64,68,72,76,

%T 80,81,84,88,90,92,96,100,104,108,112,116,120,124,125,126,128,132,135,

%U 136,140,144,148,150,152,156,160,162,164,168,172,176,180,184,188

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

%C 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 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 Robert Israel, <a href="/A355740/b355740.txt">Table of n, a(n) for n = 1..10000</a>

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Cartesian_product">Cartesian product</a>.

%F We have A001221(a(n)) >= A303975(a(n)).

%e The terms together with their prime indices begin:

%e 4: {1,1}

%e 8: {1,1,1}

%e 12: {1,1,2}

%e 16: {1,1,1,1}

%e 18: {1,2,2}

%e 20: {1,1,3}

%e 24: {1,1,1,2}

%e 27: {2,2,2}

%e 28: {1,1,4}

%e 32: {1,1,1,1,1}

%e 36: {1,1,2,2}

%e 40: {1,1,1,3}

%e 44: {1,1,5}

%e 48: {1,1,1,1,2}

%e 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 filter:= proc(n) uses numtheory, GraphTheory; local B, S, F, D, E, G, t, d;

%p F:= ifactors(n)[2];

%p F:= map(t -> [pi(t[1]), t[2]], F);

%p D:= `union`(seq(divisors(t[1]), t = F));

%p F:= map(proc(t) local i; seq([t[1], i], i=1..t[2]) end proc, F);

%p if nops(D) < nops(F) then return false fi;

%p E:= {seq(seq({t, d}, d=divisors(t[1])), t = F)};

%p S:= map(t -> convert(t, name), [op(F), op(D)]);

%p E:= map(e -> map(convert, e, name), E);

%p G:= Graph(S, E);

%p B:= BipartiteMatching(G);

%p B[1] = nops(F);

%p end proc:

%p remove(filter, [$1..200]); # _Robert Israel_, Feb 15 2024

%t primeMS[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];

%t Select[Range[100],Select[Tuples[Divisors/@primeMS[#]],UnsameQ@@#&]=={}&]

%Y Positions of 0's in A355739.

%Y The case of just prime factors (not all divisors) is A355529, odd A355535.

%Y The unordered case is counted by A355733, firsts A355734.

%Y A000005 counts divisors.

%Y A001414 adds up distinct prime divisors, counted by A001221.

%Y A003963 multiplies together the prime indices of n.

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

%Y A120383 lists numbers divisible by all of their prime indices.

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

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

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

%Y Cf. A000720, A076610, A335433, A335448, A340827, A355737, A355749, A370348.

%K nonn

%O 1,1

%A _Gus Wiseman_, Jul 22 2022