TotallyOriginallyCreatedByMe Conjecture

Consider segregating positive integers into two categories:

  • Even-type : if its prime factorization has an even number of prime(s), or it equals to 1 1 .

  • Odd-type : if its prime factorization has an odd number of prime(s).

Define

  • E ( N ) E(N) to be the number of positive integers of even-type that are less than or equals to N N

  • O ( N ) O(N) to be the number of positive integers of odd-type that are less than or equals to N N

I claim that E ( N ) O ( N ) E(N) \leq O(N) for all positive integers N N greater than 1 1 but less than 1 0 9 10^9 . Am I right?

Details and assumptions :

  • 18 = 2 × 3 × 3 18 = 2 \times 3 \times 3 , which has 3 3 prime factors, so 18 18 is an odd-type

  • 19 = 19 19 = 19 , which has 1 1 prime factor, so 19 19 is an odd-type

  • 33 = 3 × 11 33 = 3 \times 11 , which has 2 2 prime factors, so 33 33 is an even-type

  • If N = 25 N=25 , then 1 , 4 , 6 , 9 , 10 , 14 , 15 , 16 , 21 , 22 , 24 , 25 1,4,6,9,10,14,15,16,21,22,24,25 are even-type , 2 , 3 , 5 , 7 , 8 , 11 , 12 , 13 , 17 , 18 , 19 , 20 , 23 2,3,5,7,8,11,12,13,17,18,19,20,23 are odd-type . So E ( 25 ) = 12 , O ( 25 ) = 13 E(25)= 12, O(25)=13 . Which means E ( 25 ) O ( 25 ) E(25) \leq O(25) , thus it's true for N = 25 N=25 .

Yes No This problem is not clearly stated This problem does not follow Brilliant's posting rules and guidelines

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

Krishna Deb
May 11, 2014

its kinda obvious actually. but im not writing anything definite cause im not a pro at writing solutions. Just the answer : the guy is wrong in his assumption.

It's an old conjecture http://en.wikipedia.org/wiki/P%C3%B3lya_conjecture.

Hard to get the first counter-example of 906 150 257 in any easy way

David Vaccaro - 6 years, 10 months ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...