0247: "Factoring the Time"

This forum is for the individual discussion thread that goes with each new comic.

Moderators: Moderators General, Prelates, Magistrates

User avatar
Tass
Posts: 1909
Joined: Tue Nov 11, 2008 2:21 pm UTC
Location: Niels Bohr Institute, Copenhagen.

Re: "Factoring the time" Discussion

Postby Tass » Sat Feb 16, 2013 12:05 pm UTC

PsiSquared wrote:
tricky77puzzle wrote:We should try prime-factorizing Graham's number.

...wait, shit.


Since Graham's number is a power of three, factoring it would be trivially easy:

3 times 3 times 3 times 3 times 3 times 3....

The only tricky part is knowing when to stop. But given that you'll need to repeat the "3 times" waaaaaaay beyond the heat-death of the universe, I wouldn't worry about that too much.


Now do G+1

User avatar
Yakk
Poster with most posts but no title.
Posts: 11129
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: 0247: "Factoring the Time"

Postby Yakk » Sat Feb 16, 2013 2:48 pm UTC

2, ...
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

brenok
Needs Directions
Posts: 507
Joined: Mon Oct 17, 2011 5:35 pm UTC
Location: Brazil

Re: 0247: "Factoring the Time"

Postby brenok » Sat Feb 16, 2013 3:03 pm UTC

Yakk wrote:2, ...

2,2...

(G+1 finishes with 88, so it's divisible by 4)

User avatar
mathmannix
Posts: 1453
Joined: Fri Jul 06, 2012 2:12 pm UTC
Location: Washington, DC

Re: 0247: "Factoring the Time"

Postby mathmannix » Tue Feb 19, 2013 7:05 pm UTC

Can't we just say

Graham's Number = 3 ^ log_3 (Graham's Number)

and be done with it? When I prime factor 288, I don't usually say "two times two times two times two times two times three times three", I say 2^5 3^2.
I hear velociraptor tastes like chicken.

User avatar
Yakk
Poster with most posts but no title.
Posts: 11129
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: 0247: "Factoring the Time"

Postby Yakk » Tue Feb 19, 2013 8:11 pm UTC

brenok wrote:
Yakk wrote:2, ...

2,2...
(G+1 finishes with 88, so it's divisible by 4)

Exponential progress! If we keep this rate up until the heat death of the universe, exponentially factoring it with twice as many prime numbers every picosecond... we still won't have to worry about figuring out when to stop. Probably.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

User avatar
mathmannix
Posts: 1453
Joined: Fri Jul 06, 2012 2:12 pm UTC
Location: Washington, DC

Re: 0247: "Factoring the Time"

Postby mathmannix » Tue Feb 19, 2013 10:52 pm UTC

Yakk wrote:
brenok wrote:
Yakk wrote:2, ...

2,2...
(G+1 finishes with 88, so it's divisible by 4)

Exponential progress! If we keep this rate up until the heat death of the universe, exponentially factoring it with twice as many prime numbers every picosecond... we still won't have to worry about figuring out when to stop. Probably.


Well, there aren't any more 2's, or 3's, or 5's...

embernator wrote:I don't know if anyone's said this yet or not, but on igoogle there's actually an app you can put on your page that factors the time. It's 100% based on this strip


I would like a link to this please.
I hear velociraptor tastes like chicken.

rmsgrey
Posts: 3655
Joined: Wed Nov 16, 2011 6:35 pm UTC

Re: 0247: "Factoring the Time"

Postby rmsgrey » Wed Feb 20, 2013 9:57 am UTC

I sometimes do it with page numbers while reading - aiming to factorise the page number before turning the page...

PsiSquared
Posts: 126
Joined: Wed May 09, 2012 6:02 pm UTC

Re: 0247: "Factoring the Time"

Postby PsiSquared » Wed Feb 20, 2013 7:49 pm UTC

brenok wrote:
Yakk wrote:2, ...

2,2...

(G+1 finishes with 88, so it's divisible by 4)


2,2,7...

(because 36n+3+1 is always divisible by 7)

User avatar
Tass
Posts: 1909
Joined: Tue Nov 11, 2008 2:21 pm UTC
Location: Niels Bohr Institute, Copenhagen.

Re: 0247: "Factoring the Time"

Postby Tass » Wed Feb 20, 2013 8:54 pm UTC

PsiSquared wrote:
brenok wrote:
Yakk wrote:2, ...

2,2...

(G+1 finishes with 88, so it's divisible by 4)


2,2,7...

(because 36n+3+1 is always divisible by 7)


I must say. Amazing progress so far.

Ashtar
Posts: 24
Joined: Sun Jun 03, 2012 5:56 am UTC

Re: 0247: "Factoring the Time"

Postby Ashtar » Sat Mar 02, 2013 10:47 pm UTC

PsiSquared wrote:
brenok wrote:
Yakk wrote:2, ...

2,2...

(G+1 finishes with 88, so it's divisible by 4)


2,2,7...

(because 36n+3+1 is always divisible by 7)

I was doing the Wikipedia process in base 14, I can agree with this.

It's not divisible by 11, because 3^x mod 22 can't be 21, or by 13, 3^x mod 13 can't be 12. 3^(3^x) mod 17 goes through a {3, 10, 14, 7} cycle, so g_64+1 isn't divisible by 17. However, 3^(3^x)+1 is divisible by 19, for x>2. So 2,2,7,19...

PsiSquared
Posts: 126
Joined: Wed May 09, 2012 6:02 pm UTC

Re: 0247: "Factoring the Time"

Postby PsiSquared » Sun Mar 03, 2013 5:04 am UTC

Ashtar wrote:
PsiSquared wrote:
brenok wrote:
Yakk wrote:2, ...

2,2...

(G+1 finishes with 88, so it's divisible by 4)


2,2,7...

(because 36n+3+1 is always divisible by 7)

I was doing the Wikipedia process in base 14, I can agree with this.

It's not divisible by 11, because 3^x mod 22 can't be 21, or by 13, 3^x mod 13 can't be 12. 3^(3^x) mod 17 goes through a {3, 10, 14, 7} cycle, so g_64+1 isn't divisible by 17. However, 3^(3^x)+1 is divisible by 19, for x>2. So 2,2,7,19...


2,2,7,19,37...

because:
1. G+1 must be divisible by 39+1=19684=2x2x7x19x37.
2. 3^(3^x) is never congruent to -1 modulu 23, 29 or 31.
3. 3^(3^x) is never congruent to -1 module 49 or 361.

seedy
Posts: 5
Joined: Sun Feb 25, 2007 2:12 pm UTC

Re: 0247: "Factoring the Time"

Postby seedy » Mon Mar 04, 2013 10:00 pm UTC

About the Unix "factor" command, beware that your system may or may not have it compiled with the GMP library option. This makes a HUGE difference. You can tell by running the "ldd" command on it. If you don't see libgmp.so listed, you have a the slow crappy version.

For example, somebody mentioned 5000000000000000003. Here's the difference:

Code: Select all

zx81$ ldd /usr/bin/factor
        linux-vdso.so.1 =>  (0x00007ffff01ff000)
        libc.so.6 => /lib/x86_64-linux-gnu/libc.so.6 (0x00007fd3534d0000)
        /lib64/ld-linux-x86-64.so.2 (0x00007fd3538bd000)
zx81$ time /usr/bin/factor 5000000000000000003
5000000000000000003: 5000000000000000003
/usr/bin/factor 5000000000000000003  3.30s user 0.02s system 99% cpu 3.336 total
zx81$ ldd ./factor
        linux-vdso.so.1 =>  (0x00007fffdc178000)
        libgmp.so.10 => /usr/lib/x86_64-linux-gnu/libgmp.so.10 (0x00007ff407203000)
        libc.so.6 => /lib/x86_64-linux-gnu/libc.so.6 (0x00007ff406e44000)
        /lib64/ld-linux-x86-64.so.2 (0x00007ff40749f000)
zx81$ time ./factor 5000000000000000003       
5000000000000000003: 5000000000000000003
./factor 5000000000000000003  0.00s user 0.00s system 0% cpu 0.002 total
zx81$

And it also does big numbers:

Code: Select all

zx81$ /usr/bin/factor 12345678901234567890123456789012345678901234567890123456789     
/usr/bin/factor: `12345678901234567890123456789012345678901234567890123456789' is too large
zx81$ time ./factor 12345678901234567890123456789012345678901234567890123456789
12345678901234567890123456789012345678901234567890123456789: 3 3 3 7 13 31 37 61 101 211 241 2161 3541 3607 3803 9901 27961 2906161 4188901 39526741
./factor 12345678901234567890123456789012345678901234567890123456789  0.00s user 0.00s system 0% cpu 0.004 total
zx81$

Look for the latest "coreutils" package. Make sure you have libgmp-dev installed. Configure it with "CFLAGS='-march=native -O4'" and build everything. You should end up with the kickass version of factor. Astound your friends and frighten your enemies with insanely fast factoring.

Ashtar
Posts: 24
Joined: Sun Jun 03, 2012 5:56 am UTC

Re: 0247: "Factoring the Time"

Postby Ashtar » Fri Mar 08, 2013 11:24 pm UTC

PsiSquared wrote:
Ashtar wrote:
PsiSquared wrote:
brenok wrote:
Yakk wrote:2, ...

2,2...

(G+1 finishes with 88, so it's divisible by 4)


2,2,7...

(because 36n+3+1 is always divisible by 7)

I was doing the Wikipedia process in base 14, I can agree with this.

It's not divisible by 11, because 3^x mod 22 can't be 21, or by 13, 3^x mod 13 can't be 12. 3^(3^x) mod 17 goes through a {3, 10, 14, 7} cycle, so g_64+1 isn't divisible by 17. However, 3^(3^x)+1 is divisible by 19, for x>2. So 2,2,7,19...


2,2,7,19,37...

because:
1. G+1 must be divisible by 39+1=19684=2x2x7x19x37.
2. 3^(3^x) is never congruent to -1 modulu 23, 29 or 31.
3. 3^(3^x) is never congruent to -1 module 49 or 361.


3^(3^x) is never congruent to -1 modulo 41, 43, 47, 53, 61, 67, 71, 73, 79 or 83. I'm still working out 59.

PsiSquared
Posts: 126
Joined: Wed May 09, 2012 6:02 pm UTC

Re: 0247: "Factoring the Time"

Postby PsiSquared » Sun Mar 10, 2013 7:48 am UTC

Ashtar wrote:
PsiSquared wrote:
Ashtar wrote:
PsiSquared wrote:
brenok wrote:
Yakk wrote:2, ...

2,2...

(G+1 finishes with 88, so it's divisible by 4)


2,2,7...

(because 36n+3+1 is always divisible by 7)

I was doing the Wikipedia process in base 14, I can agree with this.

It's not divisible by 11, because 3^x mod 22 can't be 21, or by 13, 3^x mod 13 can't be 12. 3^(3^x) mod 17 goes through a {3, 10, 14, 7} cycle, so g_64+1 isn't divisible by 17. However, 3^(3^x)+1 is divisible by 19, for x>2. So 2,2,7,19...


2,2,7,19,37...

because:
1. G+1 must be divisible by 39+1=19684=2x2x7x19x37.
2. 3^(3^x) is never congruent to -1 modulu 23, 29 or 31.
3. 3^(3^x) is never congruent to -1 module 49 or 361.


3^(3^x) is never congruent to -1 modulo 41, 43, 47, 53, 61, 67, 71, 73, 79 or 83. I'm still working out 59.


Ruling out 59 is actually much easier than ruling out some of the other primes on your list.

By fermat's little theorem, 358=1 (mod 59)

So if 3x=-1 (mod 59) then x must be divisible by some factor of 58, which means that x cannot be a power of 3.

And the same is true for any other prime which is of the form 3n+2. (So 89 is automatically ruled out as well).

Actually, by a similar argument (I think) one can show that all the remaining factors must be of the form 27n+1. Any other factor of G+1 must also be a factor of 19684 (39+1) and we've already found all of those.

So, for all primes between 89 and 200, we only need to check two: 109 and 163. No power of three is 1 less than a multiple of 109, so it is ruled out. On the other hand:

381+162n = -1 (mod 163)

So 163 divides G+1. And our factorization is now:

2x2x7x19x37x163...

And there are no more factors under 200.

Ashtar
Posts: 24
Joined: Sun Jun 03, 2012 5:56 am UTC

Re: 0247: "Factoring the Time"

Postby Ashtar » Sun Mar 10, 2013 7:10 pm UTC

PsiSquared wrote:Ruling out 59 is actually much easier than ruling out some of the other primes on your list.

By fermat's little theorem, 358=1 (mod 59)

So if 3x=-1 (mod 59) then x must be divisible by some factor of 58, which means that x cannot be a power of 3.

I'm not sure about this. If 3^58 mod 59=1, then 3^58x mod 59=1 also. Why would the sign change?
I'd think that the only way for 3^x mod p to be congruent to p-1 would be when x=a(p-1)/(2^b), where a is odd and b is the maximum power of 2 in the prime factorization of p-1. Of course, I know next to nothing about modular arithmetic, so there's probably something I'm missing.

Yerushalmi
Posts: 23
Joined: Wed Jan 02, 2013 8:17 am UTC

Re: 0247: "Factoring the Time"

Postby Yerushalmi » Thu Oct 30, 2014 11:31 am UTC

Reading this thread years later, I'm surprised nobody's mentioned the generalized prime factor test. It works for any prime factor except 2 and 5 (whose cases are trivial).

If you want to know if x is a prime factor of y, do the following:

A) Find the lowest multiple of X that ends in a 1 or a 9. If X itself ends in a 1 or 9, great; if it ends in a 3 or 7, multiply x by 3 to get a number that does. (If X ends in anything else, it's either 2 or 5 or not prime.)
Examples: 7*3=21; 19=19; 23*3=69; 31=31

B) Round the number to the nearest multiple of ten, remove the trailing zero, and mark which direction you moved when you rounded.
Examples: 21 becomes "2 minus"; 19 becomes "2 plus"; 69 becomes "7 plus"; 31 becomes "3 minus"

C) Now we will perform the following operation on y:
i) Separate off the last digit of y
ii) Multiply the last digit of y by the number obtained in step B
iii) Perform step B's operation on y and the result of that multiple
iv) Repeat the operation on the result until you get a number that either obviously is or obviously isn't a multiple of X
Example: assume Y is 437.
Test for 7:
437 becomes 43 and 7. 7*2=14, subtract from 43 to get 29. 29 becomes 2 and 9. 9*2=18, subtract from 29 to get 11, which is not a multiple of 7, so 437 is not divisible by 7.
Test for 19:
437 becomes 43 and 7. 7*2=14, add to 43 to get 57. 57 becomes 5 and 7. 7*2=14, add to 5 to get 19. 19 is divisible by 19, so 437 is divisible by 19.
Test for 23:
437 becomes 43 and 7. 7*7=49, add to 43 to get 92. 92 becomes 9 and 2. 2*7=14, add to 9 to get 23. 23 is divisible by 23, so 437 is divisible by 23.
Test for 31:
437 becomes 43 and 7. 7*3=21, subtract from 43 to get 22. 22 is not divisible by 31, so 437 is not divisible by 31.

---------

It's a little bit complicated, but once you get used to it you can do it in your head. In addition, if you look at it carefully you'll discover that this is the general rule of which more famous divisibility tests (adding all the digits for 3 or 9, subtracting alternating digits for 11, multiplying the last digit by 2 and subtracting from the rest for 7) are but specific instances.

airdrik
Posts: 246
Joined: Wed May 09, 2012 3:08 pm UTC

Re: 0247: "Factoring the Time"

Postby airdrik » Mon Nov 24, 2014 4:43 pm UTC

That is a nice simple way of doing it. Really it boils down to:
pick a multiple of x called x' that ends in 1 or 9
for intermediate result z that starts equal to y:
if x' ends in 1 then:
1) find a number N that is a multiple of x' whose last digit matches the last digit of z
2) next z = |z - N| / 10
else
1) find a number N that is a multiple of x' whose last digit is equal to 10-(last digit of z)
2) next z = (z + N) / 10

3) Can you tell if z is or isn't a multiple of x? if so you are done, if not repeat steps 1-2

finding N is then accommodated using the whole 2+ or 7- stuff, which is a nice brain-friendly simplification that requires less digits to be stored in memory at any given point.

Now, you seem to have messed up the second pass in your first example: you subtract from the full previous result rather than just the first digit. It doesn't change the end result in that example (|2 - 18| = 16, which is also not a multiple of 7), but it would have made a difference on some of the other examples (57 + 14 = 71, which is prime; 92 + 14 = 106, which is not divisible by 23).

----------

Interesting note about the other divisibility tests is that they can be extrapolated to any basis B, applying to B-1 and B+1:
Adding the digits in base B can be used to check divisibility of B-1 and its factors (e.g. in base 9, you can use this rule for checking divisibility of 8, 4 and 2), and subtracting alternating digits can be used to check divisibility of B+1 and its factors (e.g. in base 13 (that is 9+4 to remove ambiguity in notation), you can use this rule for checking divisibility of 2, 7 and 2*7).
I didn't know about the rule for 7, but I can see how that derives from the above, 21 being the multiple of choice for 7, therefore the extension into other bases is that it applies to 2*B + 1 and factors.

Yerushalmi
Posts: 23
Joined: Wed Jan 02, 2013 8:17 am UTC

Re: 0247: "Factoring the Time"

Postby Yerushalmi » Mon Nov 24, 2014 5:36 pm UTC

Nice catch on my mess-up.

The description is necessarily more long-winded and complicated in text than it is when you're used to doing it. That's also the reason I messed up. My thought process when running through it in my head sounds something like this (dividing 406 by 7):
406
40 6
40 6 times 2 minus
40 12 minus
40 minus 12
28

By splitting it off like that, I'm no longer trying to keep the original number in mind. Putting it in text served to confuse me.


Return to “Individual XKCD Comic Threads”

Who is online

Users browsing this forum: No registered users and 114 guests