a question about A134865

[David W. Wilson]

> -----Original Message-----
> From: Max Alekseyev [mailto:maxale at gmail.com]
> Sent: Monday, May 19, 2008 9:49 PM
> To: David W. Wilson
> Cc: Don Reble; njas at research.att.com; jhbubby at mindspring.com;
> seqfan at ext.jussieu.fr
> Subject: Re: a question about A134865
> 
> On Mon, May 19, 2008 at 2:00 PM, David W. Wilson <wilson.d at anseri.com>
> wrote:
> 
> > I have a sneaking suspicion that A134865 might in fact be finite.
> 
> Just a side note.
> 
> It is strange that A005179 is not referred to in the description of
> A134865.
> Each element of A134865 is an element of A005179 (i.e., the terms of
> A134865 form a subset of the terms of A005179), and the definition can
> be stated simply as: n is in A134865 iff for every divisor d of n,
> A134865(A000005(d)) (= A140635(d)) is also a divisor of n.

I assume you meant A005179(A000005(n)), so more succinctly

%N A134865 d | n => A005179(A000005(n)) | n

However, I'm not sure I recommend this change, since this sequence should
be found by looking up "divisors" and other such words.

Anyway,

Let n be in A134865. Suppose n is not in A005179. n has d divisors, so
k = A005179(d) | n. If k were a proper divisor of n, it would have
fewer than d divisors, but by definition it has d divisors, therefore
k = n. Hence n = k = A005179(d) and n is in A005179. OK, I believe it.

> So, the question of finiteness of A134865 is closely related to the
> form of elements of A005179.

Yes, and an efficient algorithm for computing A005179(d) would greatly
Facilitate the investigation. The best I can manage is to generate
descending factorizations d = PROD e_i with e1 >= e2 >= ... >= e_k,
then taking A005179(d) = MIN PROD p_i^(e_i-1) over those factorizations.
This is slow for large d, and I can imagine some speedups (e.g,
precompute the divisor graph for d, use branch and bound to eliminate
partial products) but the programming is too much right now.

> Regards,
> Max
> 
> P.S. A140635 is a new sequence:
> 
> %I A140635
> %S A140635 1, 2, 2, 4, 2, 6, 2, 6, 4, 6, 2, 12, 2, 6, 6, 16, 2, 12, 2,
> 12, 6, 6, 2, 24, 4, 6, 6, 12, 2, 24, 2, 12, 6, 6, 6, 36, 2, 6, 6, 24,
> 2, 24, 2, 12, 12, 6, 2, 48, 4, 12, 6, 12, 2, 24, 6, 24, 6, 6, 2, 60,
> 2, 6, 12, 64, 6, 24, 2, 12, 6, 24, 2, 60, 2, 6, 12, 12, 6, 24, 2, 48,
> 16, 6, 2, 60, 6, 6, 6, 24, 2, 60, 6, 12, 6, 6, 6, 60, 2, 12, 12, 36
> %N A140635 The minimum positive integer having the same number of
> divisors as n.
> %C A140635 Clearly, a(n)<=n for all n. Moreover, a(n)=n if and only
> if n belongs to A005179.
> %F A140635 a(n) = A005179(A000005(n))
> %Y A140635 A000005, A005179
> %O A140635 1
> %K A140635 ,nonn,
> %A A140635 Max Alekseyev (maxal at cs.ucsd.edu), May 19 2008