## Search found 206 matches

Thu Apr 16, 2015 3:51 pm UTC
Forum: Logic Puzzles
Topic: Can't put a big box in a small box
Replies: 1
Views: 1914

### Can't put a big box in a small box

1. Rectangle A contains rectangle B. Must the perimeter of A >= the perimeter of B? 2. The 3-dimensional box (ie rectangular prism) A contains the 3-dimensional box B. Must the surface area of A be at least that of B? What about the sum of edge lengths -- can B be more edgy than A? 3. The n-dimensio...
Sun Mar 01, 2015 3:34 pm UTC
Forum: Coding
Topic: genetic go bot
Replies: 6
Views: 3817

### Re: genetic go bot

You may enjoy TD-gammon . It's a bot that learned how to play backgammon using a neural net. It worked using an algorithm called temporal difference learning. Two-sentence summary: you have a neural net N that predicts how well you're doing so far. If N says you're doing really well on position P, b...
Wed Feb 11, 2015 4:12 pm UTC
Forum: General
Topic: ITT: We make xkcd slightly worse.
Replies: 8673
Views: 1861366

### Re: ITT: We make xkcd slightly worse.

Fri Feb 06, 2015 12:42 pm UTC
Forum: Computer Science
Topic: Mind Blowing Algorithms
Replies: 76
Views: 29553

### Re: Mind Blowing Algorithms

I tried it, memoization speeds it up a lot. Adding memoization brings fib(10**7) from 7.896 seconds down to 0.278 seconds.

Apparently fib(10**7) makes 13333333 calls to fib, but it only calls fib on 79 distinct inputs.
Sun Jan 25, 2015 2:17 pm UTC
Forum: Logic Puzzles
Topic: Gambling with the magical genie
Replies: 27
Views: 7609

### Re: Gambling with the magical genie

> inb4 religious debate in Logic Puzzles

Will the genie let me communicate with other players? If I ally with 10 other players, then we all make a big profit even if a few of us lose. In that case, I would take this bet after seeing maybe six other players win.
Mon Jan 19, 2015 6:03 pm UTC
Forum: Computer Science
Topic: Mind Blowing Algorithms
Replies: 76
Views: 29553

### Re: Mind Blowing Algorithms

Casuals.

Code: Select all

`def fib(n):    if n<3: return [0,1,1][n]    if n%2==0: return fib(n/2+1)**2-fib(n/2-1)**2    return fib(n/2)**2+fib(n/2+1)**2x = fib(1000000) # shots fired`
Tue Jan 13, 2015 11:53 am UTC
Forum: Mathematics
Topic: Finding a (large) primitive root of a 300-digit prime
Replies: 14
Views: 6518

### Re: Finding a (large) primitive root of a 300-digit prime

Looks like a bug in repl.it.
Sat Jan 10, 2015 8:59 pm UTC
Forum: Mathematics
Topic: Finding a (large) primitive root of a 300-digit prime
Replies: 14
Views: 6518

### Re: Finding a (large) primitive root of a 300-digit prime

Disclaimer: this works, but is probably not the fastest or standard way. Let p be a large prime. If you know the factorization of p-1, you can easily test whether a given number r is a primitive root mod p. [Fact: r is a primitive root mod p unlesss there is a prime factor F of p-1 such that r (...
Fri Jan 02, 2015 4:42 pm UTC
Forum: Mathematics
Topic: Numbers easy to factor
Replies: 40
Views: 6388

### Re: Numbers easy to factor

You may want to look up the quadratic sieve, it has a similar idea to what you propose but with square numbers instead of triangular numbers. It's quite fast.
Tue Dec 30, 2014 1:38 pm UTC
Forum: Logic Puzzles
Topic: The infinite suburb and the teleporter breakdown.
Replies: 26
Views: 7526

### Re: The infinite suburb and the teleporter breakdown.

@Cradarc: The point is to get to any location in a reasonable number of hops. If I can't visit my friend at (2158096541, 1805984859403) in less than a million hops, then what's the point of having teleporters? Also, solved ekim's "every house exactly once" problem. It is possible. First, I...
Sun Dec 28, 2014 11:58 pm UTC
Forum: Logic Puzzles
Topic: The infinite suburb and the teleporter breakdown.
Replies: 26
Views: 7526

### Re: The infinite suburb and the teleporter breakdown.

Cradarc, your first solution takes linear time to get from point A to point B. I think both Nitrodon and I want a better travel time. If possible, a constant number of hops. And it doesn't look to me like Nitrodon's original three-hop solution uses all teleports of equal length. I didn't realize Nit...
Sun Dec 28, 2014 4:46 pm UTC
Forum: Logic Puzzles
Topic: The infinite suburb and the teleporter breakdown.
Replies: 26
Views: 7526

### Re: The infinite suburb and the teleporter breakdown.

...the x and y distances of each teleport must be relatively prime. Two hops are always enough. This is because you can make any teleport where either the x or y distance is 1. So to get from (0,0) to (a,b), make a stop at (1,b-1). Here's a restriction: on any given journey,...
Sat Dec 27, 2014 9:35 pm UTC
Forum: Mathematics
Topic: Trick y way about factorization
Replies: 13
Views: 3316

### Re: Trick y way about factorization

You may wish to look at existing factoring algorithms like Pollard's rho . Finding a fast factorization algorithm is a very difficult problem that thousands of people have worked on in the past. You're very unlikely to make progress on it without building on existing work. If you're trying this for ...
Fri Dec 26, 2014 2:17 pm UTC
Forum: Mathematics
Topic: Catanese Starburst
Replies: 5
Views: 2220

### Re: Catanese Starburst

Elmach wrote:There are solutions (2, 4, 6 // 7, 8, 1, 9 // 10, 5, 17, 12, 14 // 13, 15, 19, 16 // 18, 11, 3)
But 7 is next to 8, breaking OP's rule 2.
Fri Dec 26, 2014 2:00 am UTC
Forum: Mathematics
Topic: Catanese Starburst
Replies: 5
Views: 2220

### Re: Catanese Starburst

Brute force. Speed it up with backtracking or "WLOG this hex is 19". There won't be a nice mathematical argument.

EDIT: Are there even any solutions at all?
Wed Dec 24, 2014 7:57 pm UTC
Forum: Mathematics
Topic: Let us say x=y*cos(y), what does y equals in terms of x?
Replies: 6
Views: 2247

### Re: Let us say x=y*cos(y), what does y equals in terms of x?

There's no inverse in terms of elementary functions. Either get lucky with your value of x, or use a numerical approximation.
Mon Dec 22, 2014 3:54 am UTC
Forum: Science
Topic: Longest night ever, but for which timezone?
Replies: 3
Views: 1935

### Longest night ever, but for which timezone?

I heard that this solstice is the longest (or second longest) night ever (i.e. in the entire history of the Earth), because of the varying speed of the rotation of the Earth. It seems to me like this depends on which timezone you live in. Like, if your timezone's midnight lines up perfectly with the...
Thu Dec 11, 2014 2:55 am UTC
Forum: Fictional Science
Topic: two planets
Replies: 6
Views: 6651

### Re: two planets

Cool puzzle. Here's an answer that may or may not work.
Spoiler:
Think about the order the spaceships/planets were built in. The space station will have more advanced technology towards the outside, the planet will (probably) have more advanced technology near the center.
Wed Dec 03, 2014 3:36 am UTC
Forum: Mathematics
Replies: 187
Views: 278789

A fun paper about the complexity of the video game Braid. Link.

Some of you may remember this from the GISHWHES thread a billion years ago. (Long story short: Misha Collins never asked me to go on a pirate ship, so I chose not to give him an Erdos number of 3.)
Tue Nov 04, 2014 10:02 pm UTC
Forum: Logic Puzzles
Topic: Only Connect puzzles
Replies: 5
Views: 5128

### Re: Only Connect puzzles

marzis is rocking these. He/she got everything except the "Colorado River" and "Barrel" puzzles. I can't accept that answer for the "Colorado River" category, because under the circumstances, it's much too tenuous a link.
Tue Nov 04, 2014 5:05 pm UTC
Forum: Logic Puzzles
Topic: Only Connect puzzles
Replies: 5
Views: 5128

### Only Connect puzzles

Only Connect is a British quiz show about finding connections between a group of seemingly random clues. The difficulty ranges from fair to Geneva Convention-breakingly cruel. This post has a few of my favorite questions from the show, as well as one I snuck in myself. For category questions, you ha...
Fri Sep 26, 2014 5:43 pm UTC
Forum: Logic Puzzles
Topic: Eulerian paths in infinite graphs?
Replies: 15
Views: 6802

### Re: Eulerian paths in infinite graphs?

Not sure what you're getting at, ekim; your example satisfies condition (b), and it has a Eulerian path. That having been said, I think condition (b) should read "there doesn't exist a finite subgraph whose removal partitions the graph into more than one infinite connected component." It's...
Mon Sep 08, 2014 3:10 pm UTC
Forum: Logic Puzzles
Topic: Prisoners and their enemies
Replies: 21
Views: 7563

### Re: Prisoners and their enemies

Yes, that is true, Cauchy.

Spoiler:
Go ahead and color the vertices one by one. How could you possibly get stuck?
Sat Aug 09, 2014 5:57 pm UTC
Forum: General
Topic: How do you organize your files?
Replies: 21
Views: 7989

### Re: How do you organize your files?

My folders are normal (e.g. C:/Users/Me/Desktop/School). My filenames... aren't. Some filenames I've used for school assignments: - encrypted_gorefic.doc - destroyNorway.py - gregory and the misadventures of mr froggy - christmas edition - cant spell discord without disco.pdf (note: complex analysis...
Fri Aug 08, 2014 1:23 pm UTC
Forum: Mathematics
Topic: GISHWHES Erdos Number challenge
Replies: 19
Views: 5990

### Re: GISHWHES Erdos Number challenge

25. Video/Image Plagiarism - You shall not submit any items that were created by another team. Any team that is caught submitting another team’s item shall be eligible for disqualification. You may not submit any items that were taken before this year’s hunt. You may not submit any items that trigg...
Thu Aug 07, 2014 2:09 am UTC
Forum: Mathematics
Topic: GISHWHES Erdos Number challenge
Replies: 19
Views: 5990

### Re: GISHWHES Erdos Number challenge

I can actually create this level! But I don't think you want to play it. First of all, it would take a long time to create, because the Riemann Hypothesis is a complicated statement. OK, let's say I encode a simpler statement, like the Goldbach conjecture. To beat this level, you would first run aro...
Thu Aug 07, 2014 1:00 am UTC
Forum: Mathematics
Topic: GISHWHES Erdos Number challenge
Replies: 19
Views: 5990

### Re: GISHWHES Erdos Number challenge

Sorry for the double post, but I've finished a draft of the paper. You can find it here . I still have to look through it and comb for errors, sand the wording of some rough sentences, and hyper-quintuple-check that I didn't make any mistakes. Sections 1-4 are, for the most part, approachable for th...
Wed Aug 06, 2014 10:51 pm UTC
Forum: Mathematics
Topic: GISHWHES Erdos Number challenge
Replies: 19
Views: 5990

### Re: GISHWHES Erdos Number challenge

That's true. I can always put the paper on my website with Misha Collins' name on it (and a note explaining the situation), and remove his name from the version I later submit to arxiv and CoRR. BTW, the paper will be finished tomorrow. It's ~16 pages long. The first half is approachable to readers ...
Wed Aug 06, 2014 9:13 pm UTC
Forum: Mathematics
Topic: GISHWHES Erdos Number challenge
Replies: 19
Views: 5990

### Re: GISHWHES Erdos Number challenge

Tirian, I take it by your wording that you think this is a bad idea? Can you elaborate? Or am I taking your post the wrong way?

EDIT: Also, does anybody else think that this is a bad idea? I'm only an undergrad, and I don't want some big coauthorship scandal to kill my career.
Wed Aug 06, 2014 3:38 pm UTC
Forum: Mathematics
Topic: GISHWHES Erdos Number challenge
Replies: 19
Views: 5990

### Re: GISHWHES Erdos Number challenge

Out of curiosity, is giving people who had essentially no contribution to the academic content of a paper coauthorship a standard thing? I doubt it. I have heard of cases where person A invents an interesting problem, and then person B solves it, and gives A coauthorship credit. I wouldn't be surpr...
Tue Aug 05, 2014 3:04 pm UTC
Forum: Mathematics
Topic: is mathematics a religion?
Replies: 82
Views: 17252

### Re: is mathematics a religion?

I have a friend who believes that God created mathematics. That is, if God had chosen differently, the Fundamental Theorem Of Algebra might have been false, or maybe we'd be working in a system completely different from real numbers and integers. In that way, for my friend, mathematics has a religio...
Mon Aug 04, 2014 7:47 pm UTC
Forum: Logic Puzzles
Topic: Puzzle with cards
Replies: 2
Views: 2846

### Re: Puzzle with cards

Here are the letters:

Code: Select all

`f E N J xH U p t iG y A W mR p d s GS F f a`

Though I bet the puzzle is "find the correct missing card and then convert it to a letter", in which case this is useless.
Mon Aug 04, 2014 4:33 pm UTC
Forum: Mathematics
Topic: GISHWHES Erdos Number challenge
Replies: 19
Views: 5990

### Re: GISHWHES Erdos Number challenge

Hmm. This sounds like a worthy cause. I'm currently finishing up a paper about the computational complexity of the video game Braid . It's not the kind of research that will appear in a conference any time soon. But it was a surprisingly difficult question, so the paper should count for Erdos number...
Sun Jul 27, 2014 2:22 pm UTC
Forum: Mathematics
Topic: Is it possible for a math obsession to be unhealthy
Replies: 54
Views: 14557

### Re: Is it possible for a math obsession to be unhealthy

I think it's important to find people who share and understand your obsession. Try out some math competitions. If you're in high school, take the AMC 10 or AMC 12, and/or join an ARML team. If you're in college, try the Putnam. If you're in middle school, do MathCounts. Warning: the problems may be ...
Mon Jul 21, 2014 12:58 pm UTC
Forum: General
Topic: ITT: We make xkcd slightly worse.
Replies: 8673
Views: 1861366

### Re: ITT: We make xkcd slightly worse.

Thu Jul 10, 2014 4:11 pm UTC
Forum: Logic Puzzles
Topic: Lottery Ticket ................
Replies: 12
Views: 5761

### Re: Lottery Ticket ................

Maybe some kind of Pigeonhole argument will help? If you split the 49 numbers into two groups of 24 and 25, then the winning ticket is guaranteed to have three numbers from at least one group. Maybe we can buy tickets to cover each group separately. One reason this is good is that it's a lot mor...
Mon Jul 07, 2014 12:01 am UTC
Forum: Coding
Topic: Python puzzles
Replies: 20
Views: 5630

### Re: Python puzzles

Yeah, that's it! Huh, I didn't know it was implementation specific. Makes sense that other versions of Python can handle
Spoiler:
garbage collection
differently though.
Sun Jul 06, 2014 8:01 pm UTC
Forum: Coding
Topic: Python puzzles
Replies: 20
Views: 5630

### Re: Python puzzles

Hint:
Spoiler:
My solution for #1 involves defining a new class, and setting x to an instance of that class. You might find this page helpful: A Guide To Python's Magic Methods. I learned a lot of stuff from that page -- I mean, useful stuff, not just ways to make Python do weird puzzle crap.
Fri Jul 04, 2014 11:08 pm UTC
Forum: Coding
Topic: Python puzzles
Replies: 20
Views: 5630

### Re: Python puzzles

Grrr!
I'm embarrassed to say I didn't think of that.
It's not technically cheating, so... now we have two solutions!
Fri Jul 04, 2014 4:40 pm UTC
Forum: Coding
Topic: Python puzzles
Replies: 20
Views: 5630

### Re: Python puzzles

Nice! Now that we have a solution, I'll give a tiny tiny hint for my intended method: I never redefine the literal "1", or the meaning of "=". And the line "x=1" executes normally: it's in the lowest indentation level, x is an ordinary global variable, and there'...