Question

Factor \((111111)_2\) in binary

Answer 1

\[(111111)_2 = (63)_{10}\]

Answer 2

Ooooh the sum of digits of the factors is one more than the sum of digits of the original number.

Answer 3

This is related to a proof of mersenne numbers where the simplicity of factorization in binary is exploited for proving a mersenne number is not a mersenne prime

im still trying to understand how the factorization in binary is easy
let me tag the video..

Answer 4

111111=1+10+100+1000+10000+100000

so seems prime to me >.<

Answer 5

https://www.youtube.com/watch?v=NrL-9XPqXq8#t=976

Answer 6

haha i think its abut having this form
(1111....11)(1000.....0001)

Answer 7

for some reason the alternative proof using below factorization looks lot simpler to me \[2^{pq}-1 = (2^p-1)((2^{p})^{q-1} +(2^{p})^{q-2}+ \cdots + 1 )\]

how is factorization in binary better than this ? i feel im not seeing something obvious here..

Answer 8

Maybe it lends itself to some kind of byte code algorithm that happens real fast?

Answer 9

lets consider
2^p-1
it would be of the form
1111...1 up to n 1's

nw assume it have divisor of the form
(1000000...01) samw number of digits as the origion
and the other is
(1111..1) 1 digit less

Answer 10

I'm still watching the video and he just finished talking bout odd semiperfect numbers.

Answer 11

Kai skip to 15th minute

Answer 12

@Marki im following u

Answer 13

the thing is
0...0000001111111.....1 x
1000000........00000001
---------------
0...00000111111.........1 +
1...11111000000.........0
----------------------
1...11111111111..........1

Answer 14

Ohhhh this is like that problem with elevens that we were looking at several months back.

Answer 15

1001
111
----------
1001
1001
1001
-------------
111111

something like this ? but how do u know that the three 1's can be pulled out ?

Answer 16

111111 = 111(1001)

Answer 17

You know you can pull them out if there's a composite number of them I think, since it gives you a pattern that repeats

Answer 18

so for 111111 it has 6 digits lets assume first divisor have half numbers of 1's digits
111 and the other of the form 1001 , so it could work
lets see other example , shall we ?

Answer 19

lets try 2^8-1

Answer 20

yeah there is some pattern by which it can be factored i guess but i also think we need to know the factorization of 8 = 2*2*2 upfront hmm

Answer 21

\[2^8-1 = (11111111)_2\]

Answer 22

It might be nice to see how a composite number shows you how to factor it \[\large 2^{12}-1 = (111111111111)_2\] twelve factors into 1 (shown), 2, 3, 4, and 6 so we can factor it to look like these: \[11*10101010101 \\ 111*1001001001 \\ 1111*100010001 \\ 111111*1000001 \] See 2,3,4, and 6?

Answer 23

Here's all factorizations (first and last shown for completeness) 1, 2, 4, 8: \[2^8-1 \\ 1*11111111 \\ 11*1010101 \\ 1111 * 10101 \\ 11111111*1\]

Answer 24

well 2^8 and 2^12 are already composite
lets try when 2^p as p prime

Answer 25

I think it makes sense now xD
\[2^8-1 \\ 1*11111111 \\ 11*1010101 \\ 1111 * 10\color{red}{0}01 \\ 11111111*1\]

Answer 26

Whoops, well you got the point lol. Just make a space that's n-1 of 0's between the 1's so that they fall into place.

When 2^p is prime, then you can't factor it nicely I think, so it helps narrow it down. Interesting! I see now!

Answer 27

Got it completely ! thanks marki and kai :)

Answer 28

wellif n=p1...pk
then
2^n-1 divides 2^pk-1 :P

Answer 29

thats why all tries works >.<

Answer 30

lets try some prime number >.<
like
2^19-1

Answer 31

111....1 (19 digits )
so we wont be able to divide it which means it might be prime :)

Answer 32

hmm nvm

Answer 33

I see so the only primes of the form 2^n-1 have to have n be prime. Strange

Answer 34

It's kind of like a geometric argument lol

Answer 35

yes kai :)
u can prove it anyway lol
i guess ganesh and i proved it before hmm

Answer 36

I wonder if we can do a similar sort of argument in different bases. For instance, n!-1 in a factorial base?

Answer 37

In a factorial base, each digit holds a different amount, so 1=1!, 10=2!, 100=3!, 1000=4!, etc... so correspondingly, \[\Large 4! -1 = 321_{factorial} = 3*3!+2*2!+1*1!=23\]

Answer 38

interesting >.<
save this question lol

Answer 39

oh wait

Answer 40

Interesting, here's an identity I just found \[\Large n!-1 = \sum_{k=1}^{n-1}k*k!\]

Answer 41

u mean E base?

Answer 42

Yeah I think, where e is represented as a repeating decimal?

Answer 43

not sure first u mean by ! repeated 10
but then u define 4! as 24 >.<

Answer 44

Oh I see how that's confusing, so I should have written: \[1_f = 1! \\ 10_f = 2! \\ 100_f = 3! \\ 1000_f=4!\] So each digit place has a different number of digits it can contain. So I'll show you how to count to 10 in this base: \[1,10,11,20,21,100,101,110,111,120\]

Answer 45

can u define it in please >.<
like write full definition

Answer 46

I don't know how uhhhh I don't know what it's called I just found it on my own.

Answer 47

\[1_f=1_{10} \\ 10_f=2_{10} \\ 11_f=3_{10} \\ 20_f=4_{10} \\ 21_f=5_{10} \\ 100_f=6_{10} \\ \]

Answer 48

So the rightmost digit only holds 0 and 1, the next digit holds 0,1, and 2, the next digit holds 0, 1, 2, and 3, etc... So each 1000_f is a factorial, so if you see there 6=100f and 2=10f because 2 is 2! and 6 is 3! if that makes sense.

Answer 49

so
5!=100000f
5!-1=4321f

Answer 50

1
10
11
20
21
100
101
110
111
120
121
200
201
210
211
220
221
300
301
310
311
320
321
1000 :D

Answer 51

ok got it

Answer 52

Yeah! I just played around with Java and found that 12!-1 is a prime number 479001599. so it looks like 11.10.987654321 (weird since we have places that hold more than 10 in it haha XD

Answer 53

i see
12!=1000 000 000 000
12!-1=111097654321 hmm

Answer 54

so if 12!-1 is prime in f then its prime in real :O

Answer 55

that reduce lots of work >.<

Answer 56

so nw u can check numbers like
167574365! -1 :D

Answer 57

whats the largest number u can check ?

Answer 58

Some primes, but I don't know how to efficiently check them, it's not like binary so I'm trying to find a different trick that will work. But here are ones we know, maybe we can find a pattern.\[21_f = 5 \\ 321_f = 23 \\ 54321_f = 719 \\ 13,12,11,10,987654321_f= 87178291199\]

So specifically when n=3,4,6,12,14 are known primes so far. Plus we have that series formula above that might help us.

Answer 59

ur series formula hmm i still feel dull about it
u mean
(n!-1) base 10= (...) in base f ?

Answer 60

Oh that's in base 10. Sorry for the confusion XD But the idea came from looking at just the digits: \[\Large (4!-1)_{10} = 321_f = (3*3!+2*2!+1*1!)_{10}\]

Answer 61

so for n=6
(6!-1) base 10 = 1+20+300+4000+50000

Answer 62

Right, in base f.

Answer 63

yes yes and to convert to 10 again
1*1!+2*2!+....+5*5!
logic of bases :P

Answer 64

brilliant , what else ?

Answer 65

Yeah haha you understand now, awesome. XD Ok so I should show you how I first came to this before, it was in seeing: \[\Large e = \frac{1}{0!}+\frac{1}{1!}+\frac{1}{2!}+\frac{1}{3!}+... \\ \Large e = 10. \bar 1_f\]

Answer 66

i see !

Answer 67

nw this shows e is irrational in neat way :O

Answer 68

kai , write a paper about this seriously !

Answer 69

Haha I think someone else has probably found this before me. Ok so back to the problem though, I think if there is an even number of digits like \[\Large 4321_f = (4*4!+3*3!+2*2!+1*1!)_{10} =\\ \Large [(4^2+3)3! + (2^2+1)1!]_{10} \] maybe we can see something in the series?

Answer 70

never seen it with f base ?

Answer 71

n!-1= sum ((k^2+(k-1))(k-1)! ) from k=1 to n-1 ?

Answer 72

\[\Large n!-1 = \sum_{k=1}^{n-1} [(2k)^2+(2k-1)](2k)! \\ (for \ n \ odd)\]

Answer 73

note that
ohkk imissed it haha

Answer 74

wait almost

Answer 75

\[\Large n!-1 = \sum_{k=1}^{n-1} [(2k)^2+(2k-1)](2k-1)! \\ (for \ n \ odd)\]

Answer 76

no wait one more thing... XD

Answer 77

:P

Answer 78

\[\Large n!-1 = \sum_{k=1}^{(n-1)/2} [(2k)^2+(2k-1)](2k-1)! \\ (for \ n \ odd)\]

Answer 79

And I guess there's also another formula for even n as well where you just pull the 1 out. #_# but I'm sleepy not used to being up this late haha.

Answer 80

haha ok, gn anyway !
that was fun

Answer 81

Maybe we can try to figure out some thing about using them to find prime numbers or something in this funny base haha. Well, goodnight XD

Answer 82

lets check this one
(10000! -1) , in ur method it have 10000 numbers of digits but in real 35660