## 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:
**1685**

### 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:
**3356**

### 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:
**8651** - Views:
**1619148**

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

### 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.

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:
**6601**

### 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.

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:
**27488**

### 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)**2

x = 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:
**5722**

- Sat Jan 10, 2015 8:59 pm UTC
- Forum: Mathematics
- Topic: Finding a (large) primitive root of a 300-digit prime
- Replies:
**14** - Views:
**5722**

### 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:
**5526**

### 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:
**6704**

### 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:
**6704**

### 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:
**6704**

### 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:
**3039**

### 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:
**2059**

### Re: Catanese Starburst

But 7 is next to 8, breaking OP's rule 2.Elmach wrote:There are solutions (2, 4, 6 // 7, 8, 1, 9 // 10, 5, 17, 12, 14 // 13, 15, 19, 16 // 18, 11, 3)

- Fri Dec 26, 2014 2:00 am UTC
- Forum: Mathematics
- Topic: Catanese Starburst
- Replies:
**5** - Views:
**2059**

### 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?

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:
**1992**

### 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:
**1727**

### 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:
**6225**

### Re: two planets

Cool puzzle. Here's an answer that may or may not work.

**Spoiler:**

- Wed Dec 03, 2014 3:36 am UTC
- Forum: Mathematics
- Topic: Show us your articles! Or what's your Erdos number?
- Replies:
**185** - Views:
**255234**

### Re: Show us your articles! Or what's your Erdos number?

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.)

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:
**4046**

### 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:
**4046**

### 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:
**6198**

### 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:
**6444**

### Re: Prisoners and their enemies

Yes, that is true, Cauchy.

**Spoiler:**

- Sat Aug 09, 2014 5:57 pm UTC
- Forum: General
- Topic: How do you organize your files?
- Replies:
**21** - Views:
**7239**

### 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:
**5558**

### 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:
**5558**

### 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:
**5558**

### 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:
**5558**

### 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:
**5558**

### 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.

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:
**5558**

### 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:
**15033**

### 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:
**2686**

### Re: Puzzle with cards

Here are the letters:

Though I bet the puzzle is "find the correct missing card and then convert it to a letter", in which case this is useless.

Code: Select all

`f E N J x`

H U p t i

G y A W m

R p d s G

S 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:
**5558**

### 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:
**12586**

### 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:
**8651** - Views:
**1619148**

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

### 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:
**4895**

### 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 differently though.

**Spoiler:**

- Sun Jul 06, 2014 8:01 pm UTC
- Forum: Coding
- Topic: Python puzzles
- Replies:
**20** - Views:
**4895**

### Re: Python puzzles

Hint:

**Spoiler:**

- Fri Jul 04, 2014 11:08 pm UTC
- Forum: Coding
- Topic: Python puzzles
- Replies:
**20** - Views:
**4895**

### 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!

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:
**4895**

### 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'...