Dominion Strategy Forum

Please login or register.

Login with username, password and session length
Pages: 1 ... 7 8 [9] 10 11 ... 47  All

Author Topic: Maths thread.  (Read 306221 times)

0 Members and 3 Guests are viewing this topic.

liopoil

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2587
  • Respect: +2479
    • View Profile
Re: Maths thread.
« Reply #200 on: January 02, 2015, 10:30:31 pm »
0

Oh whoops, made an error with the problem. Um, we'll call that easy mode. But yea, liopoil has it right.
Okay, hard mode:

What is the least prime factor of 252^128 + 1?
So, uhh, the last digit is 7... and so the least prime factor is at the lowest 11...

252 is 10 mod 11. 10^128 + 1 is 127 0s with 1s at either end, so odd number of digits and the 1s are both in 'odd' digits, so the expression is not divisible by 11.

252 is 5 mod 13. Cycle of powers of 5 mod 13 is 5, 12, 8, 1, repeat. 128 is divisible by 4, so the expression is 2 mod 13, not divisible by 13.

252 is 12 mod 17... and I'm starting to get the feeling I need a better approach to solve this.
Logged

heron

  • Saboteur
  • *****
  • Offline Offline
  • Posts: 1055
  • Shuffle iT Username: heron
  • Respect: +1183
    • View Profile
Re: Maths thread.
« Reply #201 on: January 02, 2015, 10:58:12 pm »
0

Oh whoops, made an error with the problem. Um, we'll call that easy mode. But yea, liopoil has it right.
Okay, hard mode:

What is the least prime factor of 252^128 + 1?
So, uhh, the last digit is 7... and so the least prime factor is at the lowest 11...

252 is 10 mod 11. 10^128 + 1 is 127 0s with 1s at either end, so odd number of digits and the 1s are both in 'odd' digits, so the expression is not divisible by 11.

252 is 5 mod 13. Cycle of powers of 5 mod 13 is 5, 12, 8, 1, repeat. 128 is divisible by 4, so the expression is 2 mod 13, not divisible by 13.

252 is 12 mod 17... and I'm starting to get the feeling I need a better approach to solve this.


Yea, I wanted to make the answer big enough that you wouldn't want to just check all of the primes in order, but small enough that you can check that the number is actually prime pretty quickly.
Logged

liopoil

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2587
  • Respect: +2479
    • View Profile
Re: Maths thread.
« Reply #202 on: January 02, 2015, 11:49:42 pm »
+1

Call the value of the expression x and its least prime factor n. x is 0 mod n, so 252^128 is n - 1 mod n. Assume n < 128. Since n is prime I think (not sure) that means those cycles must have a length which is a factor of n - 1. Then (252 mod n)^ (128 mod n - 1) is n - 1 mod n. This rules out 17. Plugging in 19 we get 5 squared which is not 18 mod 19. For 23 we get 22 ^ 18, but since 22 is the first term in the cycle and 18 isn't anywhere near a factor of 22 we see it doesn't work without computation. 29 yields 20 ^ 16. Yikes. 31 yields 4 ^ 4 = 256, which is congruent to 10 (mod 31) which is not 30. Okay back to thinking more generally...

Okay maybe n > 128. I think all my statements are still true, just less useful.  I don't know what I'm doing, and am increasingly feeling like I'm entirely on the wrong track. I don't know anything about these cycles!
Logged

heron

  • Saboteur
  • *****
  • Offline Offline
  • Posts: 1055
  • Shuffle iT Username: heron
  • Respect: +1183
    • View Profile
Re: Maths thread.
« Reply #203 on: January 02, 2015, 11:58:04 pm »
0

You are more on the right track than you think.

Some things you might want to consider/hints:

I'll call the least prime factor p.
Yes, 252^128 = -1 (mod p). And yes, 252^n is periodic modulo p, where the period is a factor of p-1. Make sure you know why it is a factor of p-1.
In other words, p-1 is a multiple of the period. Now, if only you knew what the period was...
Logged

GeoLib

  • Jester
  • *****
  • Offline Offline
  • Posts: 965
  • Respect: +1265
    • View Profile
Re: Maths thread.
« Reply #204 on: January 03, 2015, 01:47:53 am »
+3

Here's a classic problem:

What is the least prime factor of 63^128 + 1?
No cheating with computers please!
Does this work?

63 = 7*3^2, so 63^128 + 1 = 7^128*3^256 + 1

The last digits of powers of 3 are 3, 9, 7, 1, repeat. 256 is divisible by 4 so the power of 3 term ends in 1.

The last digits of powers of 7 end in 7, 9, 3, 1, repeat. 128 is divisible by 4 so the power of 7 term ends in 1. Their product must also end in 1 then. Add one and the expression ends in 2. Therefore the number is divisible by 2, which is the smallest prime that there is. So the answer is 2.


So for the easy version, Can't we just say 3^256*7^128 is odd, so add one and it must be even, so 2?
Logged
"All advice is awful"
 —Count Grishnakh

Titandrake

  • Mountebank
  • *****
  • Offline Offline
  • Posts: 2210
  • Respect: +2854
    • View Profile
Re: Maths thread.
« Reply #205 on: January 03, 2015, 03:35:19 am »
+1

Ooh, I do so love a number theory puzzle. I think it's the correct answer but there are gaps in my proof that I'm working on fixing.


We want the smallest prime p such that 252^128 = -1 mod p.

Since we're always going to work mod some prime p, by Fermat's Little Theorem a^{p-1} = 1 mod p. In particular, this gives that for any k such that a^k = 1 mod p, k must be a factor of p-1. I'm sure there's a way to prove this without too much machinery, but I'll just cite Lagrange's Theorem and move on.

We know a^n is periodic in mod p. First, we need to show a^n = -1 for some n mod p.  Here's the hole: not sure how you do this.

Let k be the period, meaning the smallest positive exponent where a^k = 1. Let k' be the power such that a^k' = -1, where k' < k. Then since a^{2k'} = (-1)^2 = 1, we must have k' = k / 2. Quick proof: if k' < k/2, then 2k' < k and k cannot be the period since a^{2k'} = a^0 = 1, a contradiction. If k' > k/2, then a^{2k' - k} = 1 as well, and 2k' - k < k, also a contradiction. Therefore, we must have k' = k / 2.

So, in particular, this gives that the powers such that a^n = -1 mod p are k/2, 3k/2, 5k/2, 7k/2, ... or equivalently some odd multiple of k'. But 128 is a power of 2. Therefore, we must have k' = 128 => k = 256. So, 256 is a factor of p-1. Luckily, it turns out 257 is prime, so the answer is 257.


Edit: Have verified with computer my answer is correct. Working on the hole-filling now.

Edit 2: Some general cleaning up.
« Last Edit: January 03, 2015, 05:36:13 am by Titandrake »
Logged
I have a blog! It's called Sorta Insightful. Check it out?

heron

  • Saboteur
  • *****
  • Offline Offline
  • Posts: 1055
  • Shuffle iT Username: heron
  • Respect: +1183
    • View Profile
Re: Maths thread.
« Reply #206 on: January 03, 2015, 11:08:06 am »
0

You have the correct answer there, here is a comment and a method to prove that your answer is indeed a factor:


Yea, it is much more annoying to work with -1 mod p than with 1 mod p. It gets a lot less messy if you multiply by 252^128-1 to get 252^256 - 1. Then you know a^n = 1 mod p where n is a factor of 256, and you can quickly ascertain that n is not a factor of 128, because then p|252^128 - 1.
So 256|p-1, and as you noted, 257 is prime.

Probably the fastest way to check that 257|252^128 + 1 is via Euler's criterion for quadratic residues and quadratic reciprocity. Euler's criterion tells us that a^((p-1)/2) = 1 (mod p) if a is a quadratic residue mod p and -1 if it is a nonresidue. 252 = 7*6^2, and so (6^((257-1)/2))^2 = 1 (mod 257). So we want that 7^128 = -1 (mod 257). From the quadratic reciprocity law, 7^128 (mod 257) and 257^3 (mod 7) are either both +1 or both -1, since 7 and 257 are not both 3 (mod 4). So, 257^3 = 5^3 = -1 (mod 7), so 7^128 = -1 (mod 257). So that's it, 252^128 + 1 = 0 (mod 257). 
Logged

liopoil

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2587
  • Respect: +2479
    • View Profile
Re: Maths thread.
« Reply #207 on: January 03, 2015, 11:39:23 am »
0

Here's a classic problem:

What is the least prime factor of 63^128 + 1?
No cheating with computers please!
Does this work?

63 = 7*3^2, so 63^128 + 1 = 7^128*3^256 + 1

The last digits of powers of 3 are 3, 9, 7, 1, repeat. 256 is divisible by 4 so the power of 3 term ends in 1.

The last digits of powers of 7 end in 7, 9, 3, 1, repeat. 128 is divisible by 4 so the power of 7 term ends in 1. Their product must also end in 1 then. Add one and the expression ends in 2. Therefore the number is divisible by 2, which is the smallest prime that there is. So the answer is 2.


So for the easy version, Can't we just say 3^256*7^128 is odd, so add one and it must be even, so 2?
Or just Odd number to natural power is odd, so add one and it must be even, so 2. I didn't expect it to be so easy, so I wrote more.

Still working on the real problem, haven't read Titandrake's solution or heron's comment on it.
Logged

Kirian

  • Adventurer
  • ******
  • Offline Offline
  • Posts: 7096
  • Shuffle iT Username: Kirian
  • An Unbalanced Equation
  • Respect: +9411
    • View Profile
Re: Maths thread.
« Reply #208 on: January 04, 2015, 09:33:31 am »
+2

Here's a classic problem:

What is the least prime factor of 63^128 + 1?
No cheating with computers please!

Moat?

For some reason, this joke never gets old.
Logged
Kirian's Law of f.DS jokes:  Any sufficiently unexplained joke is indistinguishable from serious conversation.

Awaclus

  • Adventurer
  • ******
  • Offline Offline
  • Posts: 11804
  • Shuffle iT Username: Awaclus
  • (´。• ω •。`)
  • Respect: +12839
    • View Profile
    • Birds of Necama
Re: Maths thread.
« Reply #209 on: January 04, 2015, 09:47:31 am »
+4

Logged
Bomb, Cannon, and many of the Gunpowder cards can strongly effect gameplay, particularly in a destructive way

The YouTube channel where I make musicDownload my band's Creative Commons albums for free

liopoil

  • Margrave
  • *****
  • Offline Offline
  • Posts: 2587
  • Respect: +2479
    • View Profile
Re: Maths thread.
« Reply #210 on: January 04, 2015, 10:38:39 am »
0

I think we need to get more creative. Whenever I see ~5 characters of spoiler-ed text I immediately know what it says. Add some spaces at one end or something! That would make it funnier.
Logged

SwitchedFromStarcraft

  • Saboteur
  • *****
  • Offline Offline
  • Posts: 1088
  • Respect: +856
    • View Profile
Re: Maths thread.
« Reply #211 on: January 04, 2015, 10:53:34 am »
0

I think we need to get more creative. Whenever I see ~5 characters of spoiler-ed text I immediately know what it says. Add some spaces at one end or something! That would make it funnier.

Like I did in the first spoiler here:


Logged
Quote from: Donald X.
Posting begets posting.

Quote from: Asper
Donald X made me a design snob.

There is a sucker born every minute.

Awaclus

  • Adventurer
  • ******
  • Offline Offline
  • Posts: 11804
  • Shuffle iT Username: Awaclus
  • (´。• ω •。`)
  • Respect: +12839
    • View Profile
    • Birds of Necama
Re: Maths thread.
« Reply #212 on: January 04, 2015, 11:14:21 am »
+2

I think we need to get more creative. Whenever I see ~5 characters of spoiler-ed text I immediately know what it says. Add some spaces at one end or something! That would make it funnier.

But you still have to check every time.
Logged
Bomb, Cannon, and many of the Gunpowder cards can strongly effect gameplay, particularly in a destructive way

The YouTube channel where I make musicDownload my band's Creative Commons albums for free

sudgy

  • Cartographer
  • *****
  • Offline Offline
  • Posts: 3431
  • Shuffle iT Username: sudgy
  • It's pronounced "SOO-jee"
  • Respect: +2706
    • View Profile
Re: Maths thread.
« Reply #213 on: January 04, 2015, 11:44:14 am »
+3

I think we need to get more creative. Whenever I see ~5 characters of spoiler-ed text I immediately know what it says. Add some spaces at one end or something! That would make it funnier.

But you still have to check every time.

You see the spoiler, and the first thing you think when you see it, is "Is it Haha!"
Logged
If you're wondering what my avatar is, watch this.

Check out my logic puzzle blog!

   Quote from: sudgy on June 31, 2011, 11:47:46 pm

SwitchedFromStarcraft

  • Saboteur
  • *****
  • Offline Offline
  • Posts: 1088
  • Respect: +856
    • View Profile
Re: Maths thread.
« Reply #214 on: January 04, 2015, 11:47:36 am »
+5

I always check, on the theory that one day it will read "Is it Ozle?"
Logged
Quote from: Donald X.
Posting begets posting.

Quote from: Asper
Donald X made me a design snob.

There is a sucker born every minute.

sudgy

  • Cartographer
  • *****
  • Offline Offline
  • Posts: 3431
  • Shuffle iT Username: sudgy
  • It's pronounced "SOO-jee"
  • Respect: +2706
    • View Profile
Re: Maths thread.
« Reply #215 on: January 15, 2015, 03:28:02 pm »
0

So, there's something I've been wondering.  As far as I understand, here's how you solve the differential equation y' = y:

y' = y
dy/dx = y
dy/y = dx
∫dy/y = ∫dx
ln |y| = x + C
|y| = e^(x + C)
|y| = (e^x)*(e^C)
Since e^C is any positive number:
|y| = Ce^x (C > 0)
Getting rid of the absolute value allows the right side to be negative:
y = Ce^x (C ≠ 0)

The problem is, C = 0 is a solution, but I don't see how to make it a part of the process of getting the solution.
Logged
If you're wondering what my avatar is, watch this.

Check out my logic puzzle blog!

   Quote from: sudgy on June 31, 2011, 11:47:46 pm

Witherweaver

  • Adventurer
  • ******
  • Offline Offline
  • Posts: 6476
  • Shuffle iT Username: Witherweaver
  • Respect: +7861
    • View Profile
Re: Maths thread.
« Reply #216 on: January 15, 2015, 03:32:57 pm »
+1

Is it your mom?
Logged

heron

  • Saboteur
  • *****
  • Offline Offline
  • Posts: 1055
  • Shuffle iT Username: heron
  • Respect: +1183
    • View Profile
Re: Maths thread.
« Reply #217 on: January 15, 2015, 03:33:44 pm »
+4

I think the problem is that when you go from dy/dx = y to dy/y = dx, you assume that y ≠ 0.
Logged

Witherweaver

  • Adventurer
  • ******
  • Offline Offline
  • Posts: 6476
  • Shuffle iT Username: Witherweaver
  • Respect: +7861
    • View Profile
Re: Maths thread.
« Reply #218 on: January 15, 2015, 03:34:39 pm »
0

So, there's something I've been wondering.  As far as I understand, here's how you solve the differential equation y' = y:

y' = y
dy/dx = y
dy/y = dx
∫dy/y = ∫dx
ln |y| = x + C
|y| = e^(x + C)
|y| = (e^x)*(e^C)
Since e^C is any positive number:
|y| = Ce^x (C > 0)
Getting rid of the absolute value allows the right side to be negative:
y = Ce^x (C ≠ 0)

The problem is, C = 0 is a solution, but I don't see how to make it a part of the process of getting the solution.

C=0 => y=0 => y'/y does not make many senses.

Edit: Ninja'd :(
Logged

sudgy

  • Cartographer
  • *****
  • Offline Offline
  • Posts: 3431
  • Shuffle iT Username: sudgy
  • It's pronounced "SOO-jee"
  • Respect: +2706
    • View Profile
Re: Maths thread.
« Reply #219 on: January 15, 2015, 03:37:50 pm »
0

So, even though d/dx 0 = 0 it doesn't satisfy the equation y' = y?
Logged
If you're wondering what my avatar is, watch this.

Check out my logic puzzle blog!

   Quote from: sudgy on June 31, 2011, 11:47:46 pm

Witherweaver

  • Adventurer
  • ******
  • Offline Offline
  • Posts: 6476
  • Shuffle iT Username: Witherweaver
  • Respect: +7861
    • View Profile
Re: Maths thread.
« Reply #220 on: January 15, 2015, 03:42:26 pm »
0

So, even though d/dx 0 = 0 it doesn't satisfy the equation y' = y?

It satisfies the equation, but if you're going to tell me that 1 = kx (for some finite real k) and therefore 1/x = k, you're also implicitly telling me that x is not zero.
Logged

scott_pilgrim

  • Saboteur
  • *****
  • Offline Offline
  • Posts: 1102
  • Respect: +2144
    • View Profile
Re: Maths thread.
« Reply #221 on: January 15, 2015, 03:43:34 pm »
0

So, even though d/dx 0 = 0 it doesn't satisfy the equation y' = y?

Yes it does, it's an alternate solution.  Whenever you divide by a variable (this applies to basic algebra as well), you have to check whether that variable could be 0; in this case, it can.  For example, 0 is a solution of x=x^3, even though you only get 1 or -1 when you divide both sides by x.
Logged

Polk5440

  • Torturer
  • *****
  • Offline Offline
  • Posts: 1708
  • Respect: +1788
    • View Profile
Re: Maths thread.
« Reply #222 on: January 15, 2015, 03:43:55 pm »
0

So, there's something I've been wondering.  As far as I understand, here's how you solve the differential equation y' = y:

y' = y
dy/dx = y
dy/y = dx

You rule out y = 0 as a solution here because you divide by y and then integrate. You can't do this if y is identically equal to zero. So the solution method misses the trivial solution (y = 0 implies y' = 0 so that works as a solution). But normally people don't care about the trivial solutions, so it's not a big deal in this case.


[analytic details about integration go here]

Ninja'd...

Edit: scott says it better...
Logged

Witherweaver

  • Adventurer
  • ******
  • Offline Offline
  • Posts: 6476
  • Shuffle iT Username: Witherweaver
  • Respect: +7861
    • View Profile
Re: Maths thread.
« Reply #223 on: January 15, 2015, 03:45:06 pm »
0

In other words, your solution technique only finds nonzero y that solves y' = y.

Then you can simply observe that y=0 solves the equation as well, so that

y(x) = Ce^x

describes a family of solutions for all real C.
Logged

sudgy

  • Cartographer
  • *****
  • Offline Offline
  • Posts: 3431
  • Shuffle iT Username: sudgy
  • It's pronounced "SOO-jee"
  • Respect: +2706
    • View Profile
Re: Maths thread.
« Reply #224 on: January 15, 2015, 03:45:53 pm »
0

Ah, I get it now.  Thanks!
Logged
If you're wondering what my avatar is, watch this.

Check out my logic puzzle blog!

   Quote from: sudgy on June 31, 2011, 11:47:46 pm
Pages: 1 ... 7 8 [9] 10 11 ... 47  All
 

Page created in 0.058 seconds with 22 queries.