mersenneforum.org - Search Results

		mersenneforum.org > Search Forums
Search Results

Page 1 of 4

Showing results 1 to 25 of 85
Search took 0.02 seconds. Search: Posts Made By: arbooker

Forum: Miscellaneous Math

2019-09-10, 12:08

Replies: 21

33 = (8,866,128,975,287,528)³ + (-8,778,405,442,862,239)³ + (-2,736,111,468,807,040)³

Views: 2,124

Posted By arbooker

I think it's expected that there is no such...

I think it's expected that there is no such structure to the solutions here--Noam Elkies would be the person to ask.

We do make use of elliptic curves for part of the computation. You can fiber...

Forum: Miscellaneous Math

2019-09-07, 07:06

Replies: 21

33 = (8,866,128,975,287,528)³ + (-8,778,405,442,862,239)³ + (-2,736,111,468,807,040)³

Views: 2,124

Posted By arbooker

"From one solution to the next" means for that...

"From one solution to the next" means for that specific number. We still only know one solution for 33, and I'm not expecting to see the second one in my lifetime.

That's not to say that small...

Forum: Aliquot Sequences

2017-11-09, 20:48

Replies: 5

Extending an aliquot sequence backwards

Views: 7,188

Posted By arbooker

Yet more evidence that no idea is original....

Yet more evidence that no idea is original. :smile: The only thing I can think to add is the primality certificates. It's reasonable to generate them with Primo for 1000 iterations or so.

Good...

Forum: Factoring

2017-11-08, 18:59

Replies: 209

Some code for factoring numbers up to 2^63

Views: 19,908

Posted By arbooker

Nice work! I was aware of this algorithm of...

Nice work! I was aware of this algorithm of Bernstein and his toy implementation. It's nice to see an optimized version and impressive that it compares favorably to the one-off algorithms even for...

Forum: Aliquot Sequences

2017-11-08, 18:30

Replies: 5

Extending an aliquot sequence backwards

Views: 7,188

Posted By arbooker

Extending an aliquot sequence backwards

The aliquot sequence with start value 461214 is the current longest known open ended sequence starting below 1e6 (it merges with the 4788 sequence around index 6000). Right now it's just shy of 19k...

Forum: Factoring

2017-10-21, 11:02

Replies: 209

Some code for factoring numbers up to 2^63

Views: 19,908

Posted By arbooker

Here is an idea for improving the worst case...

Here is an idea for improving the worst case performance of Pollard rho.

In the factor64 code, the worst case iteration count on a large semiprime is roughly [$]cn^{1/4}[/$] for some...

Forum: Factoring

2017-10-19, 16:12

Replies: 209

Some code for factoring numbers up to 2^63

Views: 19,908

Posted By arbooker

Actually, I think that 64-bit does make a big...

Actually, I think that 64-bit does make a big difference. One of the nice features of SQUFOF is that it works with essentially half precision arithmetic. More precisely, when factoring n, most of the...

Forum: Factoring

2017-10-17, 14:53

Replies: 209

Some code for factoring numbers up to 2^63

Views: 19,908

Posted By arbooker

Thanks! I've just added the plain C...

Thanks!

I've just added the plain C functions as advertised. (Nothing changes if you're compiling on x86.) It's about 40% slower on 64-bit inputs, but only about 15% slower for <= 63 bits. Other...

Forum: Factoring

2017-10-17, 13:24

Replies: 209

Some code for factoring numbers up to 2^63

Views: 19,908

Posted By arbooker

No, it's unchanged, so if you run touch...

No, it's unchanged, so if you run

touch makefactortable
touch factor.bin
before compiling the latest version, it should be fine.

Forum: Factoring

2017-10-17, 12:46

Replies: 209

Some code for factoring numbers up to 2^63

Views: 19,908

Posted By arbooker

After a few bug fixes and small improvements, I'm...

After a few bug fixes and small improvements, I'm ready to release this on github:
https://github.com/arbooker/factor64

This code makes factor63 obsolete, so barring a massive outcry I intend to...

Forum: Factoring

2017-10-14, 16:40

Replies: 209

Some code for factoring numbers up to 2^63

Views: 19,908

Posted By arbooker

I've got a version of this working now. It's...

I've got a version of this working now. It's called factor64. :rolleyes: Before doing the github thing, I've put the source here (http://people.maths.bris.ac.uk/~maarb/code/factor64_src.tgz) in case...

Forum: Factoring

2017-10-13, 16:04

Replies: 209

Some code for factoring numbers up to 2^63

Views: 19,908

Posted By arbooker

Good point! In fact for n > 2^63, Montgomery's 1...

Good point! In fact for n > 2^63, Montgomery's 1 is just 2^64-n. So x+one never overflows, and mulredc(x,x+one) should work as expected even with 64-bit inputs.

Forum: Factoring

2017-10-13, 09:00

Replies: 209

Some code for factoring numbers up to 2^63

Views: 19,908

Posted By arbooker

With 64-bit inputs, all additions have to be...

With 64-bit inputs, all additions have to be addmods, since the computation of a+b can overflow. There is one exception to that: when x is at most n-1 you can compute mulredc(x,x+1) without risk of...

Forum: Factoring

2017-10-13, 08:52

Replies: 209

Some code for factoring numbers up to 2^63

Views: 19,908

Posted By arbooker

That's weird. There's no pleasing a temperamental...

That's weird. There's no pleasing a temperamental compiler, but it does illustrate my point that they're hard to beat when you can express your intentions clearly in C. For another illustration, I...

Forum: Factoring

2017-10-12, 22:32

Replies: 209

Some code for factoring numbers up to 2^63

Views: 19,908

Posted By arbooker

With a few exceptions, Pollard rho works with any...

With a few exceptions, Pollard rho works with any quadratic poly. Mostly people use x^2+a for some integer a. I'm using x(x+1), which when iterated starting with x=1 produces the Sylvester sequence...

Forum: Factoring

2017-10-12, 21:17

Replies: 209

Some code for factoring numbers up to 2^63

Views: 19,908

Posted By arbooker

Agreed, though I strongly favor the first...

Agreed, though I strongly favor the first solution. For PCs (or even smartphones), 180MB isn't too much memory to sacrifice these days, and despite the poor cache locality, it's still quite a bit...

Forum: Factoring

2017-10-11, 14:53

Replies: 209

Some code for factoring numbers up to 2^63

Views: 19,908

Posted By arbooker

There are actually three tables: ...

There are actually three tables:

Factorization table for small numbers. This is the largest (about 3GB in factor63) and easiest to generate--it takes just a few minutes.
Table of Pollard rho...

Forum: Factoring

2017-10-11, 09:34

Replies: 209

Some code for factoring numbers up to 2^63

Views: 19,908

Posted By arbooker

Here are few ideas for improving factor63 that I...

Here are few ideas for improving factor63 that I had after reading recent posts. Any opinions?
I could generate most of the table at compile time. That would take a few minutes but reduce the...

Forum: Factoring

2017-10-07, 10:50

Replies: 209

Some code for factoring numbers up to 2^63

Views: 19,908

Posted By arbooker

OK, at least it's working. Do you see a...

OK, at least it's working. Do you see a significant difference when run for the first time with a long test (an hour, say)? I agree that for any problem whose running time is measured in minutes or...

Forum: Factoring

2017-10-06, 23:25

Replies: 209

Some code for factoring numbers up to 2^63

Views: 19,908

Posted By arbooker

Thanks, that's a really helpful comparison. I am...

Thanks, that's a really helpful comparison. I am perplexed by the difference between user and wall time that you keep observing, though. I ran a similar test of 100k semiprimes on my system and saw...

Forum: Factoring

2017-10-06, 18:27

Replies: 209

Some code for factoring numbers up to 2^63

Views: 19,908

Posted By arbooker

Well, that turned out to be wishful thinking....

Well, that turned out to be wishful thinking. Taking this chance to look through the code again for the first time in a while, I found and fixed another bug.

There are a lot more restrictions on...

Forum: Factoring

2017-10-06, 15:16

Replies: 209

Some code for factoring numbers up to 2^63

Views: 19,908

Posted By arbooker

Obnoxious? I'm not forcing you to use it or even...

Obnoxious? I'm not forcing you to use it or even advocating it over anything else. I'm just putting the code out there in case anyone else finds it useful. This isn't the reaction that I was...

Forum: Factoring

2017-09-18, 15:39

Replies: 2

Iteration of (sigma(n)+phi(n))/2

Views: 1,703

Posted By arbooker

I would guess that asymptotically 100% of...

I would guess that asymptotically 100% of positive integers have unbounded trajectory, and it might be possible to prove something along those lines.

Note that [$](\sigma(n)+\varphi(n))/2[/$] is...

Forum: Factoring

2017-08-19, 14:44

Replies: 209

Some code for factoring numbers up to 2^63

Views: 19,908

Posted By arbooker

Some code for factoring numbers up to 2^63

While working on aliquot sequences last year, I wrote some fast code for factoring and primality testing of numbers < 2^63. I figured that it might be useful to others, so I've made it available on...

Forum: Aliquot Sequences

2016-10-22, 08:14

Replies: 43

Number of sequences that merge with any given sequence - infinite?

Views: 7,101

Posted By arbooker

Thanks for your careful reading. What I really...

Thanks for your careful reading. What I really mean there is that the chance of getting a p+1 is >> 1/k. That's based simply on the fact that the numbers grow at most like 2kn, and primes occur with...

Showing results 1 to 25 of 85

Page 1 of 4

All times are UTC. The time now is 06:41.