Extracurricular Elementary Mathematics Marathon (1 Viewer)

Paradoxica

-insert title here-
Joined
Jun 19, 2014
Messages
2,556
Location
Outside reality
Gender
Male
HSC
2016
Nice :). I actually forgot a term on the LHS from the diophantine equation I was trying to remember though lol, try the edited problem too.

It is slightly harder, but not greatly so. The original hint still stands.

Repost for visibility:

Solve the equation:



over the positive integers.

Hint: Try to determine what z can be first.




 
Last edited:

Blast1

New Member
Joined
Jan 23, 2016
Messages
12
Gender
Male
HSC
2016
Trivial for n=1.

Suppose the property holds for 1..n-1.

For general n, if their sum is divisible by n, then their sum mod n is 0. Take all elements mod n. If all elements mod n are 0, pick any subset. Otherwise, pick out an element x mod N which is nonzero mod n. 0 <= x < n. Of the remaining elements, take any n-x > 0 elements. These n-x elements have a subset divisible by n-x, so if we then add x to the subset, we have a subset with sum (n-x) + x = 0 mod N, so the subset is divisible by n.
I don't think this is quite right? Just because the sum of a subset is divisible by n-x, it doesn't necessarily mean that the sum is n-x mod N? Or have I misinterpreted what you're saying?

Here's what I had. Suppose that a_i are the elements of the set. Now, consider the sums b_i=a_1+a_2+....+a_i. If one of b_1,b_2.. b_n is 0 mod n, that set has sum divisible by n. If not, then by the pigeon hole principle, two of these are of the same class mod n. Suppose that these two are b_m and b_n, (n>m). Then, b_n-b_m has 0 mod n.

I think we need a bit of clarification here, \pi (3)= 2, but we can definitely have subintervals of length 3 which contain no prime numbers. For instance 20,21,22 is such an interval, and none of the three are prime numbers.
 
Last edited:

Blast1

New Member
Joined
Jan 23, 2016
Messages
12
Gender
Male
HSC
2016
Yes, there can be sub-intervals of length "n" with no prime numbers. however, you must prove this for all n.

And the second part is less straightforward, but still doable. The upper bound is always pi(n), because that is the maximum number of prime numbers in any sub-interval of the natural numbers of length n
?

In my previous post, I was addressing the second part of your question, not the first (I suppose I should've mentioned this). Basically, in your question you claim that if we have a subinterval of length n (has n elements), then there must exist a subinterval containing k primes for all k which exceeds 0 but is bounded by pi(x). In my previous post, I provided a counter example to this claim, showing how there exists a subinterval of length 3, but within the subinterval which I specifically mentioned (20,21,22) there is no subinterval which contains any primes. According to your question, within the subinterval (20,21,22), there should exist a subinterval which contains 1 prime and also another subinterval which contains 2 primes. Obviously, that's not true in this example.


Also, the first part of your question doesn't quite make sense either. For instance, the elements 2 and 3 form a subinterval of length 2, and clearly any subinterval within this subinterval must contain a prime. Thus your claim is false.

So this is why I'm asking for a clarification, as the question in its current wording isn't true.
 
Last edited:

seanieg89

Well-Known Member
Joined
Aug 8, 2006
Messages
2,662
Gender
Male
HSC
2007
(It suffices to show that pi(x)=o(x), which is a quite weak statement about the distribution of the primes that can be proved by a completely elementary sieving process. Am just thinking of the cleanest way to write this. Will post shortly.)
 

Paradoxica

-insert title here-
Joined
Jun 19, 2014
Messages
2,556
Location
Outside reality
Gender
Male
HSC
2016
Ahh yes, that was the other way to do it, but that was meant to be the second part to the problem. My intended solution was to use the fact that n! has n-1 obvious factors, and exploit that to construct an arithmetic progression strictly consisting of composite numbers, which is a lot easier to prove.
 

seanieg89

Well-Known Member
Joined
Aug 8, 2006
Messages
2,662
Gender
Male
HSC
2007
(It suffices to show that pi(x)=o(x), which is a quite weak statement about the distribution of the primes that can be proved by a completely elementary sieving process. Am just thinking of the cleanest way to write this. Will post shortly.)





 

seanieg89

Well-Known Member
Joined
Aug 8, 2006
Messages
2,662
Gender
Male
HSC
2007
(And yes, this is strictly more work than one needs to do to answer your original question, where a construction using a factorial explicitly gives us prime gaps of length blah. I just did it this way because I personally wanted to see how "low-tech" I could make a proof of the fact that the primes have density zero. :) )

Stronger statements about prime distribution are also very much within the scope of MX2 level techniques.

One such example is Bertrand's postulate, which states that there is at least one prime strictly between n and 2n for any positive integer n greater than 1.

This will be harder for a HS student to do without guidance, but I encourage any interested student to think about it / have a crack at it.
 
Last edited:

Blast1

New Member
Joined
Jan 23, 2016
Messages
12
Gender
Male
HSC
2016
This wording means that the question is now valid, before you said that any subinterval of length n contained a subinterval of k primes (pi(x)>k>0), which was clearly not true and hence I was confused. I would normally post my solution, but Seanieg89 has already done so and mine was pretty similar except in the part where you had to prove that there exists a subinterval with 0 primes.

 
Last edited:

seanieg89

Well-Known Member
Joined
Aug 8, 2006
Messages
2,662
Gender
Male
HSC
2007
A bit on the easier side, but just to get the ball rolling in this thread again:

A function g(n) defined on the non-negative integers satisfies:

i) g(0)=g(1)=0.

ii) g(p)=1 if p is prime.

iii) g(mn)=m*g(n)+n*g(m) for all non-negative integers m and n.


Find all n such that g(n)=n.

---------------------------------------

A somewhat harder followup question is proving that the sequence obtained by:

u(0)=63
u(n+1)=g(u(n))

tends to infinity.
 
Last edited:

Paradoxica

-insert title here-
Joined
Jun 19, 2014
Messages
2,556
Location
Outside reality
Gender
Male
HSC
2016
A bit on the easier side, but just to get the ball rolling in this thread again:

A function g(n) defined on the non-negative integers satisfies:

i) g(0)=g(1)=0.

ii) g(p)=1 if p is prime.

iii) g(mn)=m*g(n)+n*g(m) for all non-negative integers m and n.


Find all n such that g(n)=n.

---------------------------------------

A somewhat harder followup question is proving that the sequence obtained by:

u(0)=63
u(n+1)=g(u(n))

tends to infinity.
Ahh, arithmetic derivative, I have not seen you in a while.

I'll work on this later today if I get time. Otherwise, someone else can do it.
 

Users Who Are Viewing This Thread (Users: 0, Guests: 1)

Top