[Guest]

.

[Guest]

This problem is easily solved with Euler's totient function \phi(n).

With a simple application of Euler's formula for \phi(n) (look it up on wikipedia, for instance) we see that a number n is hexotic if and only if

p₁p₂...p_k=3(p₁-1)(p₂-1)...(p_k-1)

where p_i for i=1,2,...,k are the prime divisors of n arranged in increasing order.

If p_k>3 then the prime p_k divides the left hand side, but not the right hand side. This is impossible, since both sides are integers.

It is now easy to see that the hexotic numbers are precisely the numbers whose prime divisors are 2 and 3.

That is, n is hexotic if and only if n=2ⁱ3^j where i,j>0

good application of some number theory for a problem!

[Guest]

I think hexotic basically equates to numbers whose prime factorization consists of 2 and 3 with greater than 0 multiplicity, and no other prime factors (More prime factors would mean greater that 2/3 of the fractions are reducible. If that's ok, then the answer is just divisibility by 6, which seems too easy). 2^1*3^1=6, 2^2*3 =12, 2^1*3^2=18, etc. So:

1) 6

2) 6, 12, 18, 24, 36, 48 (30 is divisible by 5, and 42 divides by 7, so they're out)

3) 972 (counting back by 6s from 996 until the answer has no other factors)

6b) The proof that these numbers are all hexotic is easy, but the proof that no others are is difficult and I don't want to bother. Half the numbers from 1 to n will be divisible by 2, and so they'll be reducible by dividing numerator and denominator by 2. 1/3 will be divisible by 3, so they'll be reducible by dividing the numerator and denominator by 3. Those 2 sets overlap on the numbers divisible by 6, so the reducible fractions will be 1/2 + 1/3 - 1/6 = 2/3.

The rest I don't really care to do...

[Guest]

The hexotic numbers must have 1/3 NON-reductable fractions, so begin by considering those. Euler's function for numbers relativly prime to a given number gives e(x)=(p^(a-1))(p-1)(q^(b-1))(q-1)(r^(c-1))(r-1)... where (p^a)(q^b)(r^c)... is the prime decomposition of x. So the fraction of NON-reductables becomes e(x)/x=[(p^(a-1))(p-1)(q^(b-1))(q-1)(r^(c-1))(r-1)...]/[(p^a)(q^b)(r^c)...]. This reduces to [(p-1)(q-1)(r-1)...]/[p*q*r...]. To get this expression to equal 1/3 we must have [(2-1)(3-1)(p-1)(q-1)(r-1)...]/[2*3*p*q*r...]. In fact [(2-1)(3-1)]/[2*3] is the only fraction that works; because all other primes, p, are odd, all p-1 in the numerator will be even -- that leaves factors of 2 in the numerator that cannot be canceled by the lone 2 in the denomiator. This means that all the hexotic numbers must be of the form h=(2^a)(3^b).

.

cool puzzle. I was reading somthing the other day that I think led me to the solution rather quickly...

[Guest]

Well done all!

(and doskudos to Yagloe for the finishing touch)