wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> Odd and Even Type Integers
        
(Message started by: THUDandBLUNDER on Apr 30^th, 2004, 3:30am)

Title: Odd and Even Type Integers
Post by THUDandBLUNDER on Apr 30^th, 2004, 3:30am

Let a positive integer be of even type if its factorization into primes has an even number of primes.
Otherwise, let it be of odd type.
For example, 4 = 2*2 is of even type, while 18 = 2*3*3 is of odd type.
(Assume that 1 has zero primes and is therefore of even type.)

Let E(n) = the number of positive integers of even type [smiley=leqslant.gif] n
Let O(n) = the number of positive integers of odd type [smiley=leqslant.gif] n

Which is bigger, E(n) or O(n)?

Title: Re: Odd and Even Type Integers
Post by Benoit_Mandelbrot on Apr 30^th, 2004, 9:03am

Well, ::[hide] I beleive there should be more odd than even. If x is of odd type, so is x^3,x^5,x^7,... Because the first few numbers 2,3,5,7,8,11,... are odd as well, and because all prime numbers would also be of odd type, then there should be more odd then even. So my answer is O(n).[/hide]::

I'm going off of that prime numbers can be factored into one, being themselves, so all primes would be of odd type. I know this isn't an official explaination, but I'm just doing this off the top of my head.

Title: Re: Odd and Even Type Integers
Post by rmsgrey on May 1^st, 2004, 3:01pm

Empirically, E(1)>O(1), but up to about 70 O(n)[ge]E(n)

Title: Re: Odd and Even Type Integers
Post by Barukh on May 3^rd, 2004, 12:47am

[smiley=blacksquare.gif][hide]
Counting 1 as an integer of even type, the first n > 1 for which E(n) exceeds O(n) is 906150257 (more than 900 million!) Out of the first 1,000,000,000 numbers, 305427 have this property. The difference E(n) – O(n) reaches the record of 829 in that interval.

This problem is known as Polya’s Conjecture who strongly believed that O(n) >= E(n) is a theorem.
[/hide] [smiley=blacksquare.gif]