The idea is very nice

[iura]

Not_yet_rated Poor (Spam) Poor (Spam) Below average Below average Average Average Good Good Very good Very good Excellent

To rate posts you must be logged in

#1

The idea is very nice

[vinoth_90_2004]

Not_yet_rated Poor (Spam) Poor (Spam) Below average Below average Average Average Good Good Very good Very good Excellent

To rate posts you must be logged in

#2

yes this one is really nice ... however did you think of something like this?
first we rephrase: let q1<q2<...<q(k)<=n be squarefree numbers less than n (including q1=1). we want to prove [n/q1]+[n/q2]+...+[n/q(k)] is always odd. (this is same as the problem, since if the product of primes is always squarefree, occurs once, and if it exceeds n then [n/product of primes]=0. the product does not tho include 1, and since [n/q1]=n, its equivalant).
next let f(n) = [n/q1]...+[n/q(k)], g(n) be the number of squarefree divisors of n (not including n and 1). write out f(n) like so:
5 2 1 1
6 2 1 1
7 3 2 1 1 1
8 4 2 1 1 1
9 4 3 1 1 1
105 3 2 1 1 1
etc.
now its obvious that f(n) 'increases' from f(n-1) for every squarefree divisor of f(n-1), 1 since [n/1]=[n-1/1]+1, and a further 1 if n if squarefree, so:
f(n) = f(n-1) + g(n) + 1 if n is not squarefree
= f(n-1) + g(n) + 2 if n is squarefree
but its also obvious that g(n) is even iff n is not squarefree. so thus f(n) - f(n-1) is always even. so the parity of f(n) is always same. Checking for some n we find f(n) is always odd, which is what we wanted to prove. [sorry if i didn't explain well].

[iura]

Not_yet_rated Poor (Spam) Poor (Spam) Below average Below average Average Average Good Good Very good Very good Excellent

To rate posts you must be logged in

#3

Your proof is true vinoth and very nice.
My proof is combinatorial however.
I will post it soon.

[iura]

Not_yet_rated Poor (Spam) Poor (Spam) Below average Below average Average Average Good Good Very good Very good Excellent

To rate posts you must be logged in

#4

We prove B=sum{(-1)^l [a/p_a1*..*a_l]^2} has opposite parity with a.
Let's count The number of pairs (x,y) with 1<=x,y<=a and gcd(x,y)>1.
Let S_i be the set of pairs that satisfy p|gcd(x,y).
We must compute how many elements has the union of S1..Sk.
Applying Inclusion-Exclusion principle this number is B.
However if (x,y) is a pair then (y,x) is likewise.
So they group in pairs unless x=y.
In this case we have a-1 pairs:(2,2),(3,3)..(a,a).
So B has same parity with a-1 which implies conclusion