Project Euler problem 46

by raxu, Jun 25, 2018, 1:53 PM

The difficulty of the problem would probably depend on how far we need to check up to. If the smallest counterexample is less than $10^8$ we can find it with a naive approach, while if it's larger we would need some fancy higher math. Turns out the naive approach is enough

To check for counterexamples up to $N$ , we find list of all primes before $N$ using Eratosthenes's sieve, which runs in $O(N\log N)$ . We then create a different sieve, stepping through each $p$ and removing numbers of the form $p + 2 * k^2$ . This runs in $O(N\sqrt{N})$ .

I ran the code up to $N=10^6$ so it's fast. Turns out the counterexample is quite small!

Below is my code in Java.

public class Euler47 {
    public static void main(String[] args) {
        //We can only work with odd numbers,
        // but that is too tiring and saves a factor of 2.
        final int N = (int) 1e6; // how far we check up to
        //Eratosthenes sieve for primes
        boolean[] comp = new boolean[N];    //comp for composite
        for (int i = 2; i < N; i++)
            if (!comp[i])
                for (int j = 2 * i; j < N; j+= i)
                    comp[j] = true;
        //goldbach[i] gives if i can be achieved.
        boolean[] goldbach = new boolean[N];
        for (int p = 2; p < N; p++) {
            if (!comp[p]) for (int k = 0; p + 2 * k * k < N; k++) {
                goldbach[p + 2 * k * k] = true;
            }
        }
        for (int i = 1; i < N / 2 - 1; i++) {
            if (!goldbach[i * 2 + 1])
                System.out.printf("%d is a counterexample.%n",i * 2  +1);
        }
    }
}

This gave us $\boxed{5777}$ and $5993$ as counterexamples. Yay!

This post has been edited 2 times. Last edited by raxu, Jun 25, 2018, 1:55 PM

Trying ISL 2015 A2

by raxu, Apr 14, 2018, 2:48 PM

Find all functions $f:\mathbb{Z}\to\mathbb{Z}$ satisfying $f(x-f(y))=f(f(x))-f(y)-1.$
Let $P(a,b)$ be the equation plugging in $x=a, y=b$ .

$P(0,0): f(-f(0))=f(f(0))-f(0)-1$ , WTF...
$P(x,f(x)): f(x-f(f(x)))=-1$ , so $f(x-f(f(x)))=-1$ for all $x$ .
$P(x,x): f(x-f(x))=f(f(x))-f(x)-1$ .

What functions satisfy this? If polynomial, linear. Plug in, $m(x-my-b)+b=m(mx+b)+b-(my+b)-1$ . $f(x)=-1$ works, or $f(x)=x+1$ . As an A2, these are probably the only solutions (not a monster), but let's keep that in the back of our head.

$P(x,y|f(y)=-1): f(x+1)=f(f(x))$ . Looks like progress!
Things that didn't work: using this for previous equations, $P(x,f(x-1))$ , triple involution: $f(f(x+1))=f(f(x)+1)$ .

If $f(x)=f(y), f(f(x))=f(f(y)), f(x+1)=f(y+1), f(x)=f(x+k)=f(x+2k)=\ldots$ . Less useful than I expected.

Okay, I am bad and I glanced at the solution. Yeah I'm bad.

So we want to simplify the equation to $f(x-f(y))=f(x+1)-f(y)-1$ and show $f$ is linear. Then we are done.
$P(x+1,x): f(x+1-f(x))=-1.$

$f(x-f(x))=f(x+1)-f(x)-1, \Delta=f(x-f(x))-1=f(f(x+1-f(x))-1=f(-1)-1$ . So linear - done!

Let's see motivation: simplifying the equation should be looked at more carefully, and $P(x+1,x)$ should have been done. The hard part is thinking that our goal is to prove linearity, but notice that it's one of the only common thing our functions have.

Actually a line above probably leads to a solution I would have found.
If $f$ injective, done. Else, we know $f$ is periodic. We need to show that it's constant $-1$ .
If it's constant for big $x$ , then we can plug in a big $x$ to get $-1=f(-1)-f(y)-1, f(y)=f(-1)$ : notice this plug-in is interesting!

This post has been edited 1 time. Last edited by raxu, Apr 14, 2018, 2:59 PM

IMO problems, explained a little dankly

by raxu, Apr 14, 2018, 2:13 PM

IMO 2014 Shortlist, C1.

We might first think about trying induction, but there's a case that messes with everyone:
$[asy] size(3cm); draw((0,0)--(3,0)--(3,3)--(0,3)--cycle); draw((0,1)--(2,1)); draw((2,0)--(2,2)); draw((1,1)--(1,3)); draw((1,2)--(3,2)); [/asy]$
This shape can still have 4 points on it, but cannot be constructed inductively. Therefore, any inductive approach would likely fail. Let's call it "Bob", and say "induction failed by Bob".

We probably want a way to bound the number of rectangles using points or lines. Here are a few approaches:
1. Edges. On each edge there can be at most one point. But how in the world do I count the number of edges? Plus, Bob seems to have 8 edges, so the bound isn't strong enough.
2. Points. Each rectangle has 4 points so we have $4k$ points. $4$ of them are the original, and each point is on at least $2$ rectangles, so we have at most $2k-2$ points. But this is not strong at all... But note how $2k-2$ looks promising!
3. Number of rectangles. But on Bob, we can have a rectangle with all 4 points on it. Failed by Bob.

Another inspiration: Notice both the trivial construction (horizontal lines) and Bob are extremal, but a cross is not. Our approach should highlight this difference. What is different between them? T-junctions.
$[asy] size(3cm); draw((0,0)--(2,0)--(2,2)--(0,2)--cycle); draw((3,0)--(5,0)--(5,2)--(3,2)--cycle); draw((0,0.5)--(2,0.5));draw((0,1)--(2,1));draw((0,1.5)--(2,1.5)); draw((3,1)--(5,1)); draw((4,0)--(4,2)); [/asy]$
Rough Solution

Paying attention

by raxu, Jul 23, 2015, 2:02 PM

I've been not paying enough attention to academics recently at Mathcamp... Playing games, watching random videos, etc. I should really pay more attention!

MOP 2015

by raxu, Jun 29, 2015, 10:31 PM

Here will just be me rambling on and on about what happened at every day at MOP - I really don't want to miss anything that's even kinda close to important, since by writing this, I'll be able to look at them a few years earlier, and remember the great times I've had with my friends at MOP.
Although many of us will come to MOP again, there's a great chance almost half of us won't - After two times at MOP, a fail at the 3rd USAMO will ban you from MOP forever, and after three times, only the team can come. Adding on to the amount of people who may make mistakes on USAMO, this number is almost half.
I'm also doing these more emotional stuff before the last day, so it's not as emotional.
Therefore, below is a quick overview of what we did each day: Hope I'll be able to remember these events as I look back at it.

6/7: Arriving at MOP! Going to the airport at around 11 am, traveling as an adult... for the first time? I forgot my birth certificate, and took my passport instead

have to do the visa after I come back...
The flight went very fluently, to my surprise. Arriving at the airport, I was the last one to aboard the 3:30 bus, with Michael Ren, Allen Yang, Caleb Ji, Hongyi Chen, Junyao Peng, and the instructor Zilin Jiang. I and Zilin talked about CMU, and how I started with mathematics a little bit.
After about an hour of bus ride, we arrived at Stever! First time meeting Alex Zhai, AkshajK and a few other MOPers there, and also first time meeting my roommate Nelson. It's also the first day to try out the cafeteria food - pretty good for a university cafeteria definitely.
A little bit of mathematics, and a brief talk/opening ceremony of Po-Shen about what to do and not to should be able to finish the day. The first day of MOP is composed of a lot of "first"s.

6/8: Today will be the first day of MOP classes, as I wake up in the morning and had a hearty breakfast, with milk, peanut butter bread, etc.

Then, we're starting with our first class of the year - Graph Theory by Po-Shen! Meeting a lot of classmates, including Alex, Angela, Mihir to name a few. Then, as we're the red group, we had a class on writing better proofs, with Thomas Swayze, a very cool grader if you ever meet him. Then we had the class on HW questions, which I did on 6/7. People like Mihir trolled around on the fundamentars, while Mitchell, Alyaseed and Mark Selke managed to hold it off.
This is also the first day for me to meet Daniel Stein, one of my great friends at MOP.

6/9: From "meeting new people is fun", one can conclude "meeting new teachers is fun". We met Roxana Popescu, a young PhD student at University of Pittsburgh, who taught us about interesting stuff on floor function. Then we met Yi Sun, a PhD student at MIT, who taught us about combinatorial sums, which reminds me that I should take calculus. That handout is HARD! It's also my first day to join the singing troope, where we... sing

We also had our first MOP test today, which I felt like easier than normal. Solved 2 problems, and got a style of 0.8 in the end.

6/10: Inequaiities... I've planned at the start of MOP that my short term goal would be to finish inequalities, then functional equations, then geometry for now. We got to meet another instructor, Jennifer Iglesias, and the deputy leader of the IMO team, John Berman. It was a great lecture.
The afternoon and evening were cool with Noam Elkes here, teaching us about complex numbers and sphere packing.

6/11: Today we'll be taught by Razvan Gelca, former deputy leader of the team, and a great man to talk to. Then it was Zilin Jiang's talk on Area Methods. Despite the students were kinda trolling because he's not so good at talking in English, and that Area Methods doesn't seem to effective, Zilin was a great geometry solver. It was a great experience working with him after class.

6/12: Another graph theory class with Po-Shen! We're going to have 5 graph theory classes in total, covering all different aspects of graph theory. Today we also had our first class of bijection with Maria Gillespie, who had to leave after the 2nd week

. Today we also had the test review, where the graders briefly talk about the problems on MOP test 1 and 2. During the evening Po-Shen gave a talk on voting trees, and constructing a tree such that when we input any tournament the one that wins most other candidates will win the election. He also challenges us to solve an open problem, which no one solved... Anyway, the weekends are coming, and we're all looking forward to the weekends!

6/13-14: Weekends are busy... The below are all the events that happened.
-Conflict Kitchen: I and a few other graders and students went with John Berman to the Conflict Kitchen, a kitchen at University of Pittsburgh currently serving Cuban food. The theme of the restaurant was really interesting, and the food was great. We then visited the Cathedral of Learning at University of Pittsburgh, which reminds me of the quote "十年树木，百年树人。"
-Mock IMO: We had a Mock IMO during Saturday, where Po-Shen chose problems from ISL to give to us. The problems were even more difficult than the IMO in my opinion, with me only solving half a problem

.
-Annual run: We held our annual MOP run to a lake at Shenley park with Maria Gillespie, which a lot of people came. It was a great experience.
-t-shirt designs: since we need a MOP t-shirt, while no one has yet submitting designs, Vincent Huang decided to submit a troll design, so that people will try making great designs, or wear the design he made. A lot of great designs are created, which artistic skills I don't acquire...
-Fair Coins: Yi Sun, the instructor who was voted "hottest man at MOP", gave a talk on generating fair coins out of unfair coins. Because he loves writing heads before tails, the result keeps turning out to be heads

6/15: Today went normally, except the water shutdown, which forced us to use Mudge for the restrooms. However, this also lead us to discovering the two awesome common areas at Mudge, which were used extensively at the later days of MOP.

6/16: Plank Countdown! Although we weren't able to hold the Useless Math Olympiad, we did hold the plank countdown, where we play countdown round of Mathcounts while planking. It was a pretty fun experience.

6/17: We had our great friend Mitchell Lee giving a talk on sets with <0 elements, which turned out extremely interesting. The Stever lobby started to get used extensively now, with talks and test reviews all held there.

6/18: Po-Shen's birthday! Celebrate! Cake!

6/19: Today was one of the most interesting days of MOP. After the classes we had a philosophy session, where we and some of the staffs talked about philosophical issues, such as race, love, trying out new things, etc. Adam held a talk in the evening about a graph's minors, while he used a permanent marker at first, making his work stick on the board forever. Derp

6/20: ELMO MEETING! Today is the day for ELMO, during which we take the test return MOPers give to new MOPers. It went catastrophically for me, with I solving only 1/2 problem out of 5

6/21: Razvan, our former deputy leader, who talked to us about being a math professor at 6/12, gave a talk on torus, sphere, curves, and how they're related to physics. This is a topic on the theory he's working right now, Chern-Simons theory. A former MOPer, currently working at Dropbox, gave a talk about their company, and how Math played a major role in its development.

6/22-26: This week was the TSTST, which was fairly stressful for some people who have a chance to make TST... In the end I was able to solve #1, but my solution to #3-5 were deemed as fakesolves

. I really want to try and see if I can fix the issues in the proof and find a truthful solution in the end. Ian Le gave a talk during the time on Exceptional objects, in polyhedrons, number systems, and groups.

6/27: Today we had our MOP test 5, with some really interesting problems. #1 asks us to list the name of all MOPers; #2 was just like this year's USAMO #1; #3 was Po-Shen's research paper on diameter-2-critical graph, while #4 is a G6. We're also having our final rehearsals in Singing troope.

6/29: Student classes! This is an old tradition of MOP, where students give classes to others. This time we had Yuan Yao giving training intuitions, Michael Kural giving Projective Geometry, Yan Liu giving NT, and Vincent+Nikhil giving substitutions. Then, it's the final test review, on the TSTST and the final MOP test. Linus gave his amazing talk on complexity, and on how to solve TSTST #6.

6/30: Last day of MOP

it was a great experience here. We had our final classes, and frisbee games. We had a session on "Beyond MOP" there, where the staff talked about what they did after going to MOP. During dinner Ryan Alweiss sings "I miss the day when MOP's at Nebraska", which brought tears up to my eyes. We had the talent show, with troll acts, and also professional acts. We also had our singing troope presentations there. After the closing ceremony, it's the end of MOP. I hope that I'll see at least 65% of the people next year... It's sad to think that about 40% of the people won't come back each year... :'( But we'll keep in touch after camp

This post has been edited 7 times. Last edited by raxu, Jul 1, 2015, 4:08 PM

9th grade end - Still a few things to do!

by raxu, Jun 28, 2015, 1:58 PM

Here will be a list of things I need to do...
English:

While I didn't finish the final project, the English teacher let me pass.
Social Studies: :/ Still need the final experience... More prepping......
Science:

Everything done except sending the scores to school
Math:

Taking the test when I get back... How hard can it be lol
Art:

Pretty sure I'm done.
Computer Science:

I've done everything now at this point.

Project Euler problem 46

by raxu, Jun 25, 2018, 1:53 PM

More problems we are trying right now

by raxu, Apr 14, 2018, 7:50 PM

Trying ISL 2015 A2

by raxu, Apr 14, 2018, 2:48 PM

IMO problems, explained a little dankly

by raxu, Apr 14, 2018, 2:13 PM

Paying attention

by raxu, Jul 23, 2015, 2:02 PM

MOP 2015

by raxu, Jun 29, 2015, 10:31 PM

9th grade end - Still a few things to do!

by raxu, Jun 28, 2015, 1:58 PM

Richard's Notes :)

Project Euler problem 46

by raxu, Jun 25, 2018, 1:53 PM

More problems we are trying right now

by raxu, Apr 14, 2018, 7:50 PM

Trying ISL 2015 A2

by raxu, Apr 14, 2018, 2:48 PM

IMO problems, explained a little dankly

by raxu, Apr 14, 2018, 2:13 PM

Paying attention

by raxu, Jul 23, 2015, 2:02 PM

MOP 2015

by raxu, Jun 29, 2015, 10:31 PM

9th grade end - Still a few things to do!

by raxu, Jun 28, 2015, 1:58 PM