[seqfan] Re: A combinatorial problem

[Alois Heinz]

Vladimir Shevelev schrieb:
> Yes, you are right: here I use "arrangements" in this sense.
> Of course, a(45)=a(12) since a(n) is function of exponents of prime 
> power factorization of n only (moreover, it is invariant with respect 
> of permutations of them).
So you agree that a(45)=a(12)=3, and not 2 as in your submission?

And the values of A179926 for n =
18, 20, 28, 30, 36, 42, 44  are
 3,  3,  3, 18,  8, 18,  3, respectively, and not
 2,  2,  2, 12,  2, 12,  2, as in your submission?

Please be more careful when you submit a sequence
that can be computed so easily.

Alois
>
> Let us prove that, for n>=2, a(n)>=1. Let v(n) denote the number of 
> prime divisors of n. If v(n)=1, n=p^a, then the unique required 
> arrangement of divisors is p^a, p^(a-1),...,p,1.
> Suppose that, for m with v(m)=k and with prime divisors p_1,...,p_k, a 
> required arrangement exists. Let it be d_1=m, d_2,...,d_tau(m).
> Consider now n=m*p_(k+1)^a. For divisors of n we have an arrangement:
> d_1*p_(k+1)^a =n, d_2*p_(k+1)^a,...,d_tau(m)*p_(k+1)^a,
> d_tau(m)*p_(k+1)^(a-1), d_(tau(m)-1)*p_(k+1)^(a-1),...,d_1*p_(k+1)^(a-1),
> d_1*p_(k+1)^(a-2),...,d_tau(m)*p_(k+1)^(a-2), ...
> such that, finally, we obtain a required arrangement for divisors of n.
>
> Using this idea, for n=p_1^a_1*p_2^a_2*...*p_k^a_k, we have
>
> a(n)>=Sum {i=1,...,k}a(n/p_i^a_i)+Sum 
> {1<=i<j<=k}a(n/(p_i^a_i*p_j^a_j))*a(p_i^a_i*p_j^a_j)+...
> Therefore,on every subsequence of the form n_1,n_2,... ,when 
> v(n_1)<v(n_2)<..., sequence a(n_i) grows very fast.
>
> Regards,
> Vladimir
>