Forum: And now for something completely different
2022-05-15, 17:13
|
|
Replies: 82
Views: 3,318
Yeah. One very "trivial" improvement would come...
Yeah. One very "trivial" improvement would come to call a faster prp routine, so not call the gmp's built-in mpz_probab_prime_p function. Maybe use pfgw, or directly using the gw library. Notice that...
|
|
Forum: Factoring
2022-04-20, 23:46
|
|
Replies: 27
Views: 1,208
False, another way is to show a 1<d<n divisor,...
False, another way is to show a 1<d<n divisor, say an algebraic divisor, and then (easily) prove that d or n/d is composite, then n is not semiprime. What is also a possible case in this sequence of...
|
|
Forum: Puzzles
2022-04-17, 20:33
|
|
Replies: 3
Views: 595
All non-negative integers are reachable! ...
All non-negative integers are reachable!
consider the following 9 ways of reductions, the first number is always the starter, then we show each following numbers in the routine:
8*N+1 -> 24*N+3 ->...
|
|
Forum: Dobri
2022-04-11, 15:47
|
|
Replies: 16
Views: 1,149
On quantum computer we already have the...
On quantum computer we already have the polynomial time factorization Shor's algorithm.
I'd say it is quite unlikely that the quad binary approach would be in polynomial time using quantum [because...
|
|
Forum: Dobri
2022-04-11, 15:09
|
|
Replies: 16
Views: 1,149
|
|
Forum: Miscellaneous Math
2022-04-10, 22:37
|
|
Replies: 14
Views: 940
|
|
Forum: GMP-ECM
2022-04-01, 16:17
|
|
Replies: 24
Views: 1,786
|
|
Forum: Lounge
2022-03-15, 18:58
|
|
Replies: 169
Views: 32,530
Recent video about William Shanks, who hold the...
Recent video about William Shanks, who hold the record computation of pi for almost a century: https://www.youtube.com/watch?v=DmfxIhmGPP4
And a follow up video to find the first 100 digits of pi by...
|
|
Forum: Puzzles
2022-02-23, 15:17
|
|
Replies: 13
Views: 1,267
|
|
Forum: Puzzles
2022-02-22, 16:09
|
|
Replies: 13
Views: 1,267
That is a very nice puzzle, complete solution...
That is a very nice puzzle, complete solution (with little maths):
Work mod 5, since there are 5 different things that Penn and Teller can choose, say they have chosen x on the left and y on the...
|
|
Forum: Puzzles
2022-02-21, 12:41
|
|
Replies: 14
Views: 1,139
Hm, it is even faster:
static inline bool...
Hm, it is even faster:
static inline bool issquare(uint64_t x)
{
uint64_t sqr = 0.5+sqrt(x);
return sqr * sqr == x;
}
and gives correct answer for the full [0,2^64) range (for the same...
|
|
Forum: Puzzles
2022-02-20, 21:13
|
|
Replies: 14
Views: 1,139
It is easier:
uint64_t sqr = sqrtl(x);
return...
It is easier:
uint64_t sqr = sqrtl(x);
return sqr * sqr == x;
if you call it for 64 bits number, so 0<=x<2^64, then 0<=sqr<2^32, so it couldn't report a nonsquare number as a square, because in...
|
|
Forum: Puzzles
2022-02-20, 20:57
|
|
Replies: 14
Views: 1,139
Using one core that is true, and it is almost...
Using one core that is true, and it is almost true for many cores/threads, because we're testing res values in increasing order, just check a%M values.
Good question, but it seems that the...
|
|
Forum: Puzzles
2022-02-20, 17:50
|
|
Replies: 14
Views: 1,139
OK, but testing smaller trivial ranges is also...
OK, but testing smaller trivial ranges is also not that bad, because those contain many solutions so it is easier and quicker to find a problem, when observed that the code needs 64|M I've justed...
|
|
Forum: Puzzles
2022-02-19, 22:35
|
|
Replies: 14
Views: 1,139
OK, (almost) completely new approach.
Using...
OK, (almost) completely new approach.
Using M=100800 with t=8 threads done a=1..8000000, found 126 solutions in 1627 sec.
Roughly seven times faster what could be your code, and 20 or so times...
|
|
Forum: Puzzles
2022-02-18, 22:12
|
|
Replies: 14
Views: 1,139
|
|
Forum: MattcAnderson
2022-02-15, 22:31
|
|
Replies: 15
Views: 410
For Mathematica:
"PrimeQ first tests for...
For Mathematica:
"PrimeQ first tests for divisibility using small primes, then uses the Miller–Rabin strong pseudoprime test base 2 and base 3, and then uses a Lucas test."
ref....
|
|
Forum: MattcAnderson
2022-02-15, 17:51
|
|
Replies: 15
Views: 410
On the given link: "It returns false if n is...
On the given link: "It returns false if n is shown to be composite within one strong pseudo-primality test and one Lucas test. It returns true otherwise."
Likely they are doing some trial...
|
|
Forum: And now for something completely different
2022-02-13, 21:37
|
|
Replies: 26
Views: 2,028
|
|
Forum: Miscellaneous Math
2022-02-13, 12:43
|
|
Replies: 9
Views: 957
Do you know that for a=777 it is giving...
Do you know that for a=777 it is giving palindrome number only if n=4 ? (Generalize it for any "a" number) Inspect the numbers:
(13:38) gp > f(n)=10^n+777*10^(n-3)+1
%3 = (n)->10^n+777*10^(n-3)+1...
|
|
Forum: And now for something completely different
2022-02-11, 23:34
|
|
Replies: 26
Views: 2,028
Definitely not new result, found:...
Definitely not new result, found: https://arxiv.org/abs/1703.00826 , see table 1, only ~4 years old. But we could still write down these other proofs, at least to arxiv.org . Rob's automata approach...
|
|
Forum: And now for something completely different
2022-02-09, 17:00
|
|
Replies: 26
Views: 2,028
For any odd p prime:
T1:...
For any odd p prime:
T1: M(p-2)==(-1+kronecker(p,3))/2 mod p
T2: M(2*p-1)==3*(1+kronecker(p,3))/2 mod p
(it is also true for p=2, but you have to do the division "before" mod; p=3 could be also...
|
|
Forum: And now for something completely different
2022-02-08, 20:51
|
|
Replies: 26
Views: 2,028
|
|
Forum: And now for something completely different
2022-02-08, 19:29
|
|
Replies: 26
Views: 2,028
|
|
Forum: Lounge
2022-02-03, 21:56
|
|
Replies: 112
Views: 5,346
|
