The Nineteenth Byte

quintopia

3:02 PM

you could make it use pyprimes for the 2.0 update

Lembik

@quintopia can you explain more ?

please

@Mego is "Seriously" a programming language?

my idea which I think would win currently is this

Anonymous

@Lembik Yes, though just barely

quintopia

@Mego this is very interesting: stackoverflow.com/questions/4643647/…

Lembik

just start at powers of 2 for each one find the next two good primes.You do this by finding the next prime using codegolf.stackexchange.com/a/10702/9206n or one of the other answers there and then testing for goodness

@quintopia there is pyecm I believe

@Mego surely you don't mind implementing trial division yourself! :)

quintopia

@Lembik indeed there is

is there a python module for GNFS?

Lembik

3:11 PM

@quintopia I suspect not.

@quintopia for some reason (cough) not much public work is done on factoring very large numbers any more

Anonymous

@quintopia There's a module for everything

Lembik

msieve I think is the only easy to use tool available for large numbers

but even that doesn't seem to be developed anymore

some very important people don't want the public to factor large numbers :)

however.. in challenge the numbers aren't that big yet

Sherlock9

I used to use yafu. That was fun

Home primes and aliquot sequences

Lembik

@Sherlock9 is it plug and play or do you have to know what you are doing?

Anonymous

Hmm... Trial division would be kind of complicated to implement in Seriously

Lembik

3:13 PM

@Mego ah :)

quintopia

if you're REAL SERIOUS about factoring large numbers, of course you're going to use C...so yeah it would be surprising to have a serious py package for GNFS

Anonymous

Lots of stack manipulation

Sherlock9

You learn the command line commands, but not much otherwise

Anonymous

@quintopia Cython says hi

Sherlock9

I don't know much about how yafu works

I would recommend factordb.com as well. Great database on numbers that have been factored

Lembik

3:15 PM

sourceforge.net/projects/yafu last updated 2013

quintopia

@Mego or else you're going to use something that lets you deploy the computations to a GPU

Lembik

none of the tools seem to be currently updated!

Anonymous

> sourceforge

Anonymous

@quintopia doc.sagemath.org/html/en/reference/structure/sage/structure/…

Anonymous

Sage isn't super-fast, but it's super-nice to work with

Lembik

3:16 PM

this is great factordb.com/index.php?showid=1100000000808766929 !

smallest composite without known factors :)

Sherlock9

Godspeed @Lembik and good luck with your factoring

Lembik

@Sherlock9 does that makes sense? Isn't 88 digits < 300 bits?

Sherlock9

Do the logarithms

Lembik

I thought we could factor 300 bit numbers relatively easily

Sherlock9

Log10(2^300) = ~ 90.3, so 91 digits I think?

Lembik

3:18 PM

292 bits

for 88 digits

so surely we can factorize it!

quintopia

^^^

Sherlock9

Yeah

Takes a few minutes on yafu

Don't have it installed on this comp though

Lembik

then the website is full of nonsense!

Sherlock9

Nah, the website has many, many, many numbers to factor

I think it tries to clear out the 70-80 digit numbers that people input, first

Because the backlog gets tremendous

Their backlog of not yet factored composite numbers factordb.com/listtype.php?t=3

Hm. They're all on 88 digit numbers

Anonymous

It's a monumentous, probably-poorly-funded undertaking

Lembik

3:21 PM

trying msieve

Sherlock9

Well, I guess it takes a few minutes, but it could be up to half an hour IIRC from my factoring days

Lembik

first question..how do you actually use it?!

Anonymous

Can you really blame them for not having factored every number yet?

Sherlock9

There is usually a README of some sort

Lembik

I am reading the readme

Sherlock9

3:22 PM

Alright send me a link

Lembik

./msieve
cannot open input file 'worktodo.ini'

@Sherlock9 sourceforge.net/projects/msieve

still can't find any useful docs

Sherlock9

Trying opening it in Notepad++ if you have it

Lembik

I can compile msieve no problem

just can't work out how to give it the number to factor!

Anonymous

Sourceforge is generally bad

Lembik

ok got it to do something

running with some randomly chosen command line flags...

@Sherlock9 maybe you could compete with yafu :)

and see who finishes first

Sherlock9

3:26 PM

I have started running it now

TimmyD

Ew, Sourceforge link

2

Sherlock9

This is yafu I have literally just downloaded

Lembik

which command line flags?

@Sherlock9 great!

Sherlock9

And the comp I'm on is slow and dumb

Lembik

like me :)

Sherlock9

3:26 PM

yafu-Win32.exe factor(12)

That's all I needed to type

Well, I put in your number instead of 12, obviously

Lembik

so much easier!!

Sherlock9

How'd you get msieve to work?

I want to try it now :)

Lembik

put the number in worktodo.ini

if you then run msieve with no options I am not sure exactly what it does... try it with 12 as the number :)

is yafu running for you?

msieve says

sieving in progress (press Ctrl-C to pause)
524 relations (508 full + 16 combined from 19381 partial), need 57763

currently

the official advice is to use the quadratic sieve for numbers with < 90 digits

so if you can work out how to choose that that would be great

Sherlock9

Yafu is running. Msieve as downloaded won't

Says it's missing a dll

Lembik

ah.. windows?

Sherlock9

3:32 PM

Yup

Lembik

not my area sorry

Sherlock9

Fair enough

Lembik

maybe we could have a ppcg challenge to implement the quadratic sieve

Sherlock9

I think the quadratic sieve is already running for you, from the looks of it

And that challenge would probably be won by Peter Taylor because a) he's probably the only person I know who would know how that works and b) he's a madman

Lembik

@Sherlock9 right but ... let me show you the issue.If I put 12 into worktodo.ini and run msieve I get no output

Sherlock9

3:34 PM

Nice.

Lembik

oh I have to look in the log it seems!

@Sherlock9 P. Taylor is not a madman! He simply has a good degree from a good university :)

hah... python -m primefac 24 ! 1 - 38 ! 1 + :)

python has a factorization module it turns out

quintopia

wat

Lembik

it's not too slow either

factor the numbers 24! - 1 = 620448401733239439359999 and 38! + 1 = 523022617466601111760007224100074291200000001.

Sherlock9

Did it work on your 88-digit number?

Lembik

@Sherlock9 no.. I am leaving msieve to do that.. which I assume is much more professional

quintopia

3:38 PM

wow primefac looks p good

Lembik

I just factored 620448401733239439359999 and 52302261746660111176000722410007429120000000 using primefac

Sherlock9

I quit on yafu. 24 mins. Yeesh

I'm going to do a few more things before I try that again

Lembik

is 24 minutes the predicted time?

Sherlock9

Nope. The predicted time for that stage

Lembik

you know you can factor numbers from the command line in unix!

factor 620448401733239439359999
620448401733239439359999: 625793187653 991459181683

:)

as long as it is < 2^127

I bet you can't do that in windows :)

Sherlock9

3:40 PM

Factordb finished on your number before either of us could factordb.com/…

Lembik

really??

that's funny if true

Sherlock9

Look at the link

factordb.com/…

Lembik

who did it?

I mean are they changing regularly?

like every few minutes

Sherlock9

The database has its own factoring thing. It's not just a repository of numbers.

Lembik

oh.. so they are running some code on every composite number

and the code has just got to this one?

Sherlock9

3:42 PM

Yep and yep

Lembik

does this make sense?

I mean if you are doing every number isn't it more efficient to sieve?

Sherlock9

They're not doing every number

Lembik

no?

what are they doing?

Sherlock9

Just the ones people input

Or the ones in the sequences people ask about

Lembik

oh.. why do people input 88 digit numbers??

Sherlock9

3:45 PM

Why are you inputting 88 digit numbers?

Lembik

at least I now have a good feeling for how long it takes to factor an 88 digit number :)

@Sherlock9 I am downloading it.. not inputting it :)

Sherlock9

What do you mean?

Lembik

Oh I see. you mean my coding challenge

ok so it is just people wasting their time :)

Sherlock9

A) There's a lot of factoring projects going on all the time

B) That isn't a nice way to put it

Lembik

I wonder what code they run.. do you know?

yafu and msieve seem too slow

at least using their default settings

Sherlock9

3:47 PM

Not sure

I'm messing with yafu settings right now actually

Lembik

great!

does it try to guess which method to use?

Sherlock9

Something like that

I'm a little too tired to explain something I don't understand much about though

Lembik

do you know if there are gpu versions?

it's all a little slow on a single cpu :)

Sherlock9

Point is, up to about 30-40 digits it uses ECM, then 40-80 digits on one of the NFS, and the other NFS after

Lembik

"The latest version of msieve supports polynomial selection using an NVIDIA GPU which is an order of magnitude faster than using the CPU. "

apparently yes :)

Sherlock9

3:49 PM

You can set how many threads it should use

Lembik

oh I missed that!

silly me

Sherlock9

Got any other numbers that need factoring?

Lembik

@Sherlock9 well... factordb does! I can't see how to set the thread number in msieve in fact

factordb.com/index.php?showid=1100000000808766958

I am really surprised it is so hard to factor an 88 digit number!

Sherlock9

The universe is 10^80 cubic meters. I'm surprised it's not harder

Lembik

:) that's a funny measure

quintopia

4:03 PM

meters? ha!

how many cubic planck lengths is it?

Lembik

cubic teaspoons?

quintopia

that would be hard to use

Lembik

what is a small-radix repunit ?

eprint.iacr.org/2014/653.pdf

"Given long-term projects such as [10, 11, 6] where many factoring-
enthusiasts worldwide constantly busy themselves to factor many special numbers, such as
for instance small-radix repunits, it makes sense to investigate whether factoring efforts that
are eagerly pursued no matter what can be combined to save on the overall amount of work"

quintopia

well i'd guess a repunit is a number like 1111111111111111 (since a repdigit is a repeating digit)

Lembik

thanks

I didn't know people like factorizing those :)

oh msieve finished

TimmyD

4:10 PM

Repunit

In recreational mathematics, a repunit is a number like 11, 111, or 1111 that contains only the digit 1 — a more specific type of repdigit. The term stands for repeated unit and was coined in 1966 by Albert H. Beiler in his book Recreations in the Theory of Numbers. A repunit prime is a repunit that is also a prime number. Primes that are repunits in base 2 are Mersenne primes. == Definition == The base-b repunits are defined as (this b can be either positive or negative) Thus, the number Rn(b) consists of n copies of the digit 1 in base b representation. The first two repunits base b for n=1...

Sherlock9

@quintopia 10^195

Lembik

Fri Dec 11 16:06:08 2015 prp34 factor: 1935593649167422056388731646101733
Fri Dec 11 16:06:08 2015 prp55 factor: 1606317434847773480628408493855802388914788844367233749

now let's see if that was right

looks right

if it was 500 times faster I would be impressed :)

Sherlock9

C89 is finished

C89 being a term for that 89-digit composite number you were talking about

factordb.com/…

Much, much too slow on my comp though

quintopia

@Sherlock9 that's more like it. still factorable tho.

Lembik

hmm.. this factoring must be done by users

it's too fast to be done by their computers

Sherlock9

4:17 PM

@quintopia In about the lifetime of the universe

Until quantum computers get kicking

Lembik

which number is too large?

Sherlock9

10^195

@Lembik Nope. The computers over there do the factoring

Lembik

ah yes.. well governments can do it I assume

"The computers over do the factoring"?

I mean 10^195 is about 600 bits, right?

Sherlock9

The users check some of the numbers, but FactorDB can factor too

Lembik

if it is just factordb doing the factoring I want to know how!!?

Sherlock9

4:19 PM

@Lembik Ish. But after 110 digits, it takes days

@Lembik Me too, but I'm not the one to ask

Lembik

@Sherlock9 sure.. unless you spent $500 million dollars on the computer :)

Sherlock9

Price doesn't ensure CPU or GPU processing capability. It can help though

Besides 195 digits is still huge.

Come to think of it though RSA-512 took a manner of CPU-weeks

Might still be possible to do 195. In a few years

Lembik

@Sherlock9 well.. if you have $500 million dollars you can buy a lot of expertise too

768 bits has already been done back in 2009

that is more than 195 digits

Sherlock9

Ah fair enough

It's been a while. I don't remember much from that time before my computers were crud

... Around six months ago, I was still heavily into this stuff

Yeah, my memory is shite

Lembik

:)

Sherlock9

4:24 PM

Alright what else you got

I'm enjoying getting back into this stuff

Where are you getting these numbers?

Lembik

4:35 PM

@Sherlock9 this is just in relation to my good prime puzzle I think

Sherlock9

Ah, I see

FactorDB does primality testing pretty quickly, you know

Lembik

for my problem you need to test for prime powers

which is slightly different

Sherlock9

Ah, I see

Well then what other numbers are you testing today?

Lembik

I am not really sorry.... if you want to win my challenge please feel though :)

18

Q: Find the largest gap between good primes

Following the fine tradition of questions such as Find the largest prime whose length, sum and product is prime , this is a variant on a largest prime challenge. Input Your code should not take any input. Definition We say a prime p is good if p-1 has exactly 2 distinct prime factors. Output...

Sherlock9

I've seen it

I'm not really good at writing fast code. Or factorization code

Lembik

4:50 PM

I think my doubling idea will win it..

@Sherlock9 it only needs prime power testing code

and I think really it only needs someone to implement my doubling idea :)

@Sherlock9 which language do you like to code in?

Sherlock9

Python. But I have two problems

Lembik

pyth and on?

Sherlock9

I am on a crap computer tonight and most of tomorrow

I don't have Pypy installed on this one

But show me your doubling idea. I'll see what I can do

Lembik

if you just wanted to help you could write code that uses libraries that are not allowed and show us some big gaps

the doubling idea is really simple.. just start at powers of two and search for the next two good primes after each one

that's it

I suspect that would win currently

Cᴏɴᴏʀ O'Bʀɪᴇɴ

@FlagAsSpam Still, it seems less objectable.

New Sandboxed Posts

4:58 PM

0

A: Sandbox for Proposed Challenges

Unique Prime Factors of Repunits code-golf primes The Background We were talking prime factorization in chat and came across repunits. Repunits are a subset of the numbers known as repdigits, which are numbers consisting of only repeating digits, like 222 or 4444444444444444, but repunits cons...

SuperJedi224

5:15 PM

Hello

TimmyD

@SuperJedi224 Hello

Sherlock9

@Lembik You were bloody right

I just got 8868

And my code isn't even good

Posting it quickly and then off to bed

Lembik

@Sherlock9 :)

Sherlock9

Posted it

Still a little shell-shocked

mbomb007

Does anyone know who made tryitonline.net ?

Lembik

5:28 PM

how do you check the primes are good?

@Sherlock9 I sometimes have good ideas :)

Sherlock9

It is pretty bad code

Trial division

Ok, if I slow it down by asking it to keep running if the good primes found aren't far enough apart, it gets 4284

SuperJedi224

Graphical 2-dimensional golfing language... good idea?

Sherlock9

I've got to go to bed @Lembik. I'll do some more testing in the morning

Lembik

good night!

SuperJedi224

@Sherlock9 Goodnight

Sherlock9

5:35 PM

@Lembik Oh and on one final note, my posting very likely doesn't meet your criteria

Look it over on your question, and give me some comments

Lembik

@Sherlock9 because?

Sherlock9

Because I didn't read your criteria :P

And now, I really must get going. Goodnight

Lembik

bye

mbomb007

@quartata Sometimes even using Mathematica expressions doesn't work.

Nathan Merrill

is there a "recent chat rooms" list?

quartata

5:42 PM

@AlexA. What's QWOP?

@mbomb007 This is true. :/

mbomb007

@quartata It's a game. Look it up and play it.

It's online and takes no time. Unless you want to spend hours trying to win.

Because it's really hard.

QWOP

Dennis

@mbomb007 <-

quartata

@mbomb007 Our overlord Dennis.

New Main Posts

0

Q: Point in convex hull

This is a first try. Here are the rules: input: N+1 2-D coordinates (N >= 3) stored in a raw text file "./input" under the following format: 0.00;0.00 1.00;0.00 0.00;1.00 1.00;1.00 output: 1 printed to stdout (or your language equivalent) if the first point in the list (...

code-golf

Cᴏɴᴏʀ O'Bʀɪᴇɴ

5:57 PM

\o/ finished my GOL-based language

SuperJedi224

@CᴏɴᴏʀO'Bʀɪᴇɴ Yay! Link?

quintopia

as in...implemented it?

quintopia

6:16 PM

i liked your quora post on esolangs

SuperJedi224

6:47 PM

@quintopia Thanks

mbomb007

@Dennis Nice! Not all the languages in the list are implemented yet, are they? I tried SMBF, and I don't think it was working.

Or did you use the original interpreter?

What I mean is: the original interpreter(s) do not interpret dynamic code created on or to the right of the initial location of the pointer. This is, imho, a bug in the original interpreter that prevents it from following its own spec.

Dennis

@mbomb007 The index is dynamic. All listed languages are implemented. I used the C interpreter IIRC.

mbomb007

A simple test: ++++++++++++++++++++++++++++++++++++++++++++++ (46*'+') should generate a period . on the tape. This period is not, but should be, executed, printing itself.

Transcript for