[QUOTE=CRGreathouse]I'm trying to figure out what you mean by "general composite". In post #187 you define it to mean the same as "composite", but in that case why did you say "general composite" in post #157 rather than just "composite"?
[/QUOTE]

Initially, I meant "general semiprimes", due to the comparisons between how many bases a 2nd kind Cunningham semiprime is pseudoprime to, compared to a general semiprime.

Ex: 63727551014401 = 5644801 * 11289601 vs. 289481332205123 = 7056779 * 41021737

Here are the false witness results:
The latter: No false witness below 1 million.
The former: Too many false witnesses to count. (Begins 1, 5, 7, 10, ..)

And this has been the consistent result for all comparisons between a 2nd kind Cunningham and a general semiprime. An explanation why is a Google search away, I guess.
My best guess is that the 2nd kind Cunninghams I am using have many prime factors when 1 is subtracted from them, and that is somehow correlated to the amount of false witnesses that they produce.

I'm going to try 2nd kind Cunninghams that lack so many prime factors whenever 1 is subtracted from them, to test my bullshit idea.

Debunked - Even when the only prime divisor that was necessarily there is two, here's the false witness sequence:

1, 2, 4, 6, 7, 8, 9, 16, 18, 21, 24, 28, 32, 36, 42, 49, 50, 54, 63, 64, 72, 75, 81, 84, 85, 96, 98, 112, 128, 142, 144, 145, 150, 162, 168, 170, 175, 185, 189, 190, 191, 196, 200, 213, 216, 235, 252, 255, 256, 263, 285, 288, 290, 293, 294, 295, 300, 305, 307, 323, 324, 336, 337, 340, 343, 350, 358, 359, 378, 382, 384, 392, 401, 409, 419, 421, 426, 435, 441, 448, 450, 451, 454, 461, 486, 497, 503, 512, 521, 523, 525, 526, 533, 537, 541, 551, 554, 555, 567, 568, 570, 576, 578, 580, 583, 600, 605, 610, 625, 629, 631, 646, 648, 665, 672, 674, 675, 680, 681, 682, 689, 698, 700, 703, 705, 715, 722, 727, 729, 740, 745, 751, 756, 760, 764, 765, 784, 789, 799, 800, 802, ...


Whatever gives 2p^2-p so many false witnesses..

[QUOTE=CRGreathouse;224842]That would wait for user input 99 times. Surely that's not what you want?

Ideally, the program wouldn't directly ask for user input at all. That way I could write a program that checks mersenneforum.org for updates, read those updates into a string, and send the string to the program, which would either output a program or give some sort of an error.

So if it read a post that said

it might generate something like
[code]userscript_mersenneforum_post83529()={
forprime(p=1,100,print(p))
};
addhelp(userscript_mersenneforum_post83529, "userscript_mersenneforum_post83529(): Lists the primes p with 1 <= p <= 100. Assumes that 100 <= default(primelimit).")[/code]
and if it reads something like

it just gives
[code]*** user error: cannot determine program from description[/code][/QUOTE]

I was thinking of making pari write the program itself before taking over the world lol (just joking about the taking over the world). no I don't want to ask users input 99 times I'd have to make a variable then that = Vec(input) then check that vector.

I need to learn to read more lol.

maybe if it finds something it can't decipher it could suggest questioning about what it can't figure out.

a program making a program seems like a virus but this idea sounds cool. one thing I've thought of is using a text to speech translator like what Microsoft has in Windows(though if possible better) and instead of turning it to speech interpret its meaning and spit out a program based on what it can understand(hopefully a lot).

Well, a promising clue is right [URL="http://www.math.dartmouth.edu/~carlp/PDF/lower.pdf"]here[/URL].

[QUOTE=3.14159;224845]Initially, I meant "general semiprimes", due to the comparisons between how many bases a 2nd kind Cunningham semiprime is pseudoprime to, compared to a general semiprime.[/QUOTE]

Unfortunately I tossed my earlier code. But I can rewrite it readily enough. And better this time!

Let's see... how to go about generating a random semiprime. Suppose we want one in the range (a, b] with b - a large compared to log^2 b and b/a small. There are [TEX]\pi(b/3) - \pi(a/3)\approx(b-a)/3\log b[/TEX] semiprimes divisible by 3, etc. So to choose the size of the smaller prime factor we give each prime weight equal to its reciprocal and select from the total size at random.

So if the range is (2^99, 2^100] then we want to give 2 weight 1/2, 3 weight 1/3, ..., and 1125899906842597 weight 1/1125899906842597. (I'm going to ignore issues about choosing toward the end of the range here.) The total weight is going to be about [url=http://oeis.org/classic/A077761]M[/url] + log log sqrt b.* So generate a random number uniformly at random up to that total, subtract M, and exponentiate twice, choosing a prime around there. Then generate the other factor as appropriate.


* Dusart's recent preprint gives reasonably tight bounds on this. Pity, though, I don't know of a correcting term, because there certainly seems to be one.

[SPOILER]Alternatively, you could just multiply two random primes together. No need for much math work on generating a set of random primes to multiply together to form a semiprime.[/SPOILER]

Wait.. disregard the above.

[QUOTE=3.14159;224849]Well, a promising clue is right [URL="http://www.math.dartmouth.edu/~carlp/PDF/lower.pdf"]here[/URL].[/QUOTE]

I'm familiar with that paper. Also of interest is "On the distribution of pseudoprimes" which he published the following year, giving an upper bound,

But I thought you were looking at strong pseudoprimes, not Fermat pseudoprimes. In that case "Average case error estimates for the strong probable prime test" is probably more appropriate, though I don't remember if they define an analogue for P(x).

[QUOTE=science_man_88;224848]I was thinking of making pari write the program itself before taking over the world lol (just joking about the taking over the world).[/QUOTE]

I'm not sure which one would be harder.

[QUOTE=science_man_88;224848]a program making a program seems like a virus but this idea sounds cool.[/QUOTE]

Agreed. I've written program that generate other programs -- even as a child, I wrote a bitmap graphics program that would output a BASIC program drawing what you wanted (so that I could include it in my own program, naturally).


[QUOTE=science_man_88;224848]one thing I've thought of is using a text to speech translator like what Microsoft has in Windows(though if possible better) and instead of turning it to speech interpret its meaning and spit out a program based on what it can understand(hopefully a lot).[/QUOTE]

That sounds harder yet.

I suggest breaking the task down into simple parts and working on them separately. That way you won't get discouraged by the difficulty of the whole task -- and you can have something that you can finish in an hour rather than in a lifetime.

lets say it was on the same computer all together we have:

1) read the problem to the script
2) decipher the meaning of the problem
3) output a code that does what the problem needs.


the main one when it's on one computer is 2) decipher the meaning of the problem.

example if the problem is read as:

find all primes from x upto/until/to n

the key words/phrasings I see are 1)find - suggest to most I think that they may not necessarily want to have them printed to them but to get them for further use (though printing is a further use in one sense)

2)all primes-means they don't want any missed.

3)from-shows us there's a range involved and that that range may be anywhere on the number line (so we can just assume 1 in this case).

4)x-our lower limit if it's odd if not it's x+1 (except when x = 2) that is our lower limit.

5) upto/until/to- these all mean in the positive direction last i checked.

6) n-our upper bound.

so generically they want:

[CODE]forprime(p=x,n,do something else/likely print())[/CODE]

or if any number in range x...n is out of primelimit bounds

[CODE]for(p=x,n,if(isprime(p),do something else/likely print()))[/CODE]

in this case we used every word but in more vague cases or less specific cases it might not be so.

Agreed, 2 does seem the hardest. 1 is easy.

So why don't you focus on #3. It's not completely trivial, but unlike #2 it isn't a lifetime research project. :smile:

[QUOTE=CRGreathouse;224856]Agreed, 2 does seem the hardest. 1 is easy.

So why don't you focus on #3. It's not completely trivial, but unlike #2 it isn't a lifetime research project. :smile:[/QUOTE]

doesn't 3 depend on 2 ?

I used the words to decipher the meaning and in doing so I was able to give possible codes.

OK, here's my program for generating random semiprimes. It's not perfect, but it gives reasonable results I think. And the speed should be fast even when working with large numbers.

If you need higher-quality results, you'd want correction factors for M when generating p and a different method entirely for selecting q. The first takes mathematical knowledge and programmer time to implement, but wouldn't make the program run much more slowly at all; the second takes little time to implement (< 10 minutes) but would cause the program to run perhaps ~100 times more slowly at large numbers.

[code]rsp(b,flag=0)={
if(b<7,
if(b<3, error("No semiprimes with fewer than 3 bits"));
if(type(b) != "t_INT", error("Bad type in rsp"));
my(n);
if(b==3,n=[4,6]);
if(b==4,n=[9,10,14,15]);
if(b==5,n=[21,22,25,26]);
if(b==6,n=[33,34,35,38,39,46,49,51,55,57,58,62]);
n=n[random(#n)+1];
return(if(flag,factor(n),n))
);

\\ Choose the small prime as 2 with probability 1/2, 3 with probability 1/3, etc.
my(M=.261497212847642783755,weight=log(b*log(2)/2)+M,r=random(round(weight << 64))*1.>>64,p=precprime(exp(exp(r-M))),q);
q=2^b\p;
q=nextprime(q\2+random(q\2));
if(p > q,
b = p;
p = q;
q = b;
);
if(flag,
if(p==q,
matrix(1,2,i,j,if(j==1,p,2))
,
[p,1;q,1]
)
,
p*q
)
};
addhelp(rsp, "rsp(b, {flag=0}): Generates a random b-bit semiprime. If flag is nonzero, returns the factorization of the number.");[/code]

[QUOTE=science_man_88;224857]doesn't 3 depend on 2 ?[/QUOTE]

It doesn't have to. Suppose your program works like this:

[code]foo(name, description)={
\\ stuff goes here that figures out what the user wants
if (userDesire == 1,
print("forprime(p="start","stop","func");")
return;
);
if (userDesire == 2,
print("isprime("start");")
return;
);
if (userDesire == 3,
error("i'm afraid I can't do that, Dave.")
);
error("Bad user desire code")
};[/code]

You could work out code that goes in the blocks above, even without filling in the part with the comment. Of course you could only use it by calling those functions you create directly...

interesting idea...

dictionary for step 2 with different wordings leading to a main math word that they describe.

that math word can be linked to specific codes to help put it in practice.

[QUOTE=science_man_88;224887]interesting idea...

dictionary for step 2 with different wordings leading to a main math word that they describe.

that math word can be linked to specific codes to help put it in practice.[/QUOTE]

Right. I would put each of them in its own function and document what the function does. If you ever got a natural language processor working, you can have it read the addhelp statements to determine which one is appropriate to use. :smile:

eg. primorial = prime factorial || primorial (well dah) || multiplication of primes upto n || multiplication of the first n primes

is there a way to equate 2 names to a function one to mean the other. if so should be easy

oh wait I could do this:

[CODE]primorial(n)= a=1;for(p=1,n,if(isprime(p),a=a*p));return(a)

prime_factorial(n)=primorial(n)

multiplication_of_primes_upto(n) = primorial(n)[/CODE]


then all these are equal and the code should be able to put the words into a function name and figure it out regardless.

they all work as planned I tested them.

Right. Actually I'd just code the first and let the AI (#1) figure out that they're all the same.

[QUOTE=CRGreathouse;224891]Right. Actually I'd just code the first and let the AI (#1) figure out that they're all the same.[/QUOTE]


I'm not sure how to do this in AI yet (I do have a uncle in robotics teaching last I checked wonder if someone like that would help) maybe I should have learned KPL lol

AI is artificial intellegence but it seems like AI is also automatically inferred

I meant to also say: your method of defining function synonyms is good. (It avoids duplication, which is bad.)

Another possibility would be literally
[code]prime_factorial=primorial[/code]
that is, setting the variable prime_factorial equal to the value of primorial, which is itself a 'function-object'. (Pari calls this a "closure".)

[QUOTE=science_man_88;224892]I'm not sure how to do this in AI yet maybe I should have learned KPL lol

AI is artificial intellegence but it seems like AI is also automatically inferred[/QUOTE]

I meant it in the sense of artificial intelligence. The essential problem is deciding what the human wants and that's a classic strong-AI task.

yeah the equals is good see what i was thinking is:

if someone said:

"multiplication of primes upto"

it would replace " " with "_" and get a function name it can look for.

think the hard part then is:

1)size of the database
2)printing the code the function uses not the function itself(unless it makes it part of their database first).

Fortunately you can print functions (as closures) in the development version, which I'm sure you downloaded rather than the old 'stable' version.

[code]foo(n)={
if(n%7 == 4,
print(n" is a foo");
1
,
print(n" is not a foo");
0
)
};
print(foo)[/code]

[QUOTE]Reading GPRC: /cygdrive/c/Program Files/PARI/.gprc ...Done.

GP/PARI CALCULATOR Version 2.4.2 (development CHANGES-1.1971)
i686 running cygwin (ix86/GMP-4.2.1 kernel) 32-bit version
compiled: Dec 23 2007, gcc-3.4.4 (cygming special, gdc 0.12, using dmd 0.125)
(readline v5.2 enabled, extended help enabled)

Copyright (C) 2000-2006 The PARI Group

PARI/GP is free software, covered by the GNU General Public License, and comes WITHOUT ANY
WARRANTY WHATSOEVER.[/QUOTE]

looks like it to me.

how is this like prime_factorial=primorial ? this seems to print the code of foo but doesn't equate it to another function but I think I know what you mean. This is getting less complicated by the minute, (though the database might get quite big and that's a mountain to climb).

[QUOTE=CRGreathouse]But I thought you were looking at strong pseudoprimes, not Fermat pseudoprimes. In that case "Average case error estimates for the strong probable prime test" is probably more appropriate, though I don't remember if they define an analogue for P(x).
[/QUOTE]

Well, I did manage to get the complete false witness sequence for 2701. It is pseudoprime to 486 bases. That means, it will be registered as composite 82% of the time.

[QUOTE=3.14159;224899]Well, I did manage to get the complete false witness sequence for 2701. It is pseudoprime to 486 bases. That means, it will be registered as composite 82% of the time.[/QUOTE]

[code]isSPRP(n,b=2)={
my(s=valuation(n-1,2),d=n>>s);
n=Mod(b,n)^d;
if(n==1,return(1));
while(s--,
if(n==-1,return(1));
n=n^2
);
n==-1
};
ratioSlow(n)={
1.-sum(b=1,n-1,isSPRP(n,b))/(n-1)
};
star(n)={
n--;n>>valuation(n,2)
};
ratio(n)={
my(f=factor(n)[,1],nu=valuation(f[1]-1,2),nn=star(n));
for(i=2,#f,nu=min(nu,valuation(f[i]-1,2)););
1.-(1+(2^(#f*nu)-1)/(2^#f-1))*prod(i=1,#f,gcd(nn,star(f[i])))/(n-1)
};[/code]

[code]>ratio(2701)
time = 31 ms.
%1 = 0.8200000000000000000000000000

>ratioSlow(10^6+1)
time = 34,071 ms.
%2 = 0.9962500000000000000000000000
>ratio(10^6+1)
time = 0 ms.
%3 = 0.9962500000000000000000000000[/code]

Ah, thanks. Although, I do have it perform trial division for isSPRP, up to 10[sup]6[/sup]. isPRP does not perform trial division.


Also: Define star(n) (I haven't defined it already.)

You used 2701, which was a bad case. Here are some other bad bases and their ratios:

[code]A141768=[9, 25, 49, 91, 341, 481, 703, 1541, 1891, 2701, 5461, 6533, 8911, 12403, 18721, 29341, 31621, 38503, 79003, 88831, 146611, 188191, 218791, 269011, 286903, 385003, 497503, 597871, 736291, 765703, 954271, 1024651, 1056331, 1152271, 1314631];
for(i=1,#A141768,print(ratio(A141768[i])"\t"A141768[i]))[/code]
gives something like
[code]0.750000000 9
0.833333333 25
0.875000000 49
0.800000000 91
0.852941176 341
0.887500000 481
0.769230769 703
0.842857143 1541
0.761904762 1891
0.820000000 [COLOR="Red"]2701[/COLOR]
0.838461538 5461
0.838028169 6533
0.800000000 8911
0.754716981 12403
0.835576923 18721
0.861963190 29341
0.835483871 31621
0.752688172 38503
0.751879699 79003
0.751773049 88831
0.751381215 146611
0.751219512 188191
0.751131221 218791
0.751020408 269011
0.750988142 286903
0.750853242 385003
0.750750750 497503
0.750684931 597871
0.750617283 736291
0.750605326 765703
0.750542299 954271
0.765217391 1024651
0.750515464 1056331
0.758884636 1152271
0.750462107 1314631[/code]

For more, see the b-file.

[QUOTE=3.14159;224901]Ah, thanks. Although, I do have it perform trial division for isSPRP, up to 10[sup]6[/sup]. isPRP does not perform trial division.[/QUOTE]

I'm not sure what trial division gets you here.

[QUOTE=3.14159;224901]Also: Define star(n) (I haven't defined it already.)[/QUOTE]

I edited it in before you posted this. :smile: Sorry, I had it in the sequence but initially forgot to include it here.

[QUOTE=CRGreathouse]I edited it in before you posted this. Sorry, I had it in the sequence but initially forgot to include it here.
[/QUOTE]

I looked in the sequence and found it. Now, the code works just fine.

I made a base counter as well:

[code]bcount(n) = {
n = n * (1-(ratio(n)))
}[/code]

Corrections: 1-(ratio(n)) needs another set of parentheses. Corrections made.

[QUOTE=3.14159;224904]I made a base counter as well:[/QUOTE]

That's already in the sequence! I just modified it to give the ratio, since that's what you cared about. Use *that* program, not the one you posted, since rounding errors will be important here.

Testing for primes: Expected result, every base registers prime.

[QUOTE=CRGreathouse]That's already in the sequence! I just modified it to give the ratio, since that's what you cared about. Use *that* program, not the one you posted, since rounding errors will be important here.
[/QUOTE]

Nope, it just gives how often it will be marked off as composite.

The base counter naturally followed. Rounding errors? Why did you make a program that was inaccurate? :lol:!

[QUOTE=3.14159;224906]The base counter naturally followed. Rounding errors? Why did you make a program that was inaccurate? :lol:![/QUOTE]

I made it output the result in floating-point because you gave the result as 0.82 rather than 41/50. It would be easy to modify the program to give an exact rational -- but why compute the sum, convert to a ratio, then convert back?


I don't understand what you mean by
[QUOTE=3.14159;224906]Nope, it just gives how often it will be marked off as composite.[/QUOTE]
or if I'm supposed to respond to it.

[QUOTE=3.14159;224906]Why did you make a program that was inaccurate? :lol:![/QUOTE]

I'm sure people could ask you that same question :lol:

[QUOTE=CRGreathouse]I made it output the result in floating-point because you gave the result as 0.82 rather than 41/50. It would be easy to modify the program to give an exact rational -- but why compute the sum, convert to a ratio, then convert back?
[/QUOTE]

Seeing as it works just fine for small numbers (I would rarely need it for large integers), it works for me!

[QUOTE=CRGreathouse]I don't understand what you mean by...or if I'm supposed to respond to it.[/QUOTE]

Nevermind that..

[QUOTE=science_man_88]I'm sure people could ask you that same question :lol:[/QUOTE]

And this statement, coming from one who can't properly define his own terminology, 97% of the time? Right, and the moon is made of cheese. :missingteeth:

[QUOTE=science_man_88;224908]I'm sure people could ask you that same question :lol:[/QUOTE]

True enough. My program gave the floating-point number closest to the exact quantity, but Pi's program suffers from [url=http://docs.sun.com/app/docs/doc/800-7895/6hos0aou8?a=view]catastrophic cancellation[/url] that may give wildly inaccurate results for large enough numbers and small enough precision. (They don't have to be that large or that low, even!)

[QUOTE=3.14159;224909]Prime powers always have n-1 bases hat register it as pseudoprime. :tu:[/QUOTE]

You can see that just from examining the program: it looks only at the [url=http://oeis.org/classic/A007947]radical[/url] of the number.

so the basic idea I have of the process required is:

1)read for updates
2)send request to next part of script
3)find function names that can be understood in the text (if none exist give error and/or print questions the script has about the request)
4)print out code for functions if they are found to be in the database.
5) post code to Mersenne forums website.

hard part about this now is mostly with if 2 functions need to be embedded with each other later (I've already worked out how to print 2 functions one after the other but not inside each other).

oh and one step i missed to check for names that use underscore instead of space we'd need a way to turn all spaces into underscores

I think it would just be a vector read and replace operation myself.

[CODE]if(v[i]==" ",v{i]=="_")[/CODE]

[QUOTE=science_man_88;224913]so the basic idea I have of the process required is:

1)read for updates
2)send request to next part of script
3)find function names that can be understood in the text (if none exist give error and/or print questions the script has about the request)
4)print out code for functions if they are found to be in the database.
5) post code to Mersenne forums website.[/QUOTE]

Sounds good. #3 is the hard part, #4 is the part I suggested working on. #1 and #5 are doable but not very useful until the others are done. (Also, compared to #2 and #3 those steps are fairly unfun.)

I think your first task should be #0: split the large tasks #2 and #3 into smaller subtasks (5-10 tasks each, if you can manage).

[QUOTE=science_man_88;224914]hard part about this now is mostly with if 2 functions need to be embedded with each other later (I've already worked out how to print 2 functions one after the other but not inside each other).[/QUOTE]

What are you trying to do that would require a function inside a function?

[QUOTE=science_man_88;224914]oh and one step i missed to check for names that use underscore instead of space we'd need a way to turn all spaces into underscores

I think it would just be a vector read and replace operation myself.

[CODE]if(v[i]==" ",v{i]=="_")[/CODE][/QUOTE]

Yes, that would work, and the resulting vector can be concatenated back to a string. But if you start with a string "What are the first 10 Mersenne primes?" you don't really want to call the function What_are_the_first_10_Mersenne_primes, but rather something like firstMersenne(10). It's not an easy problem by any means!

[QUOTE=CRGreathouse;224916]

Yes, that would work, and the resulting vector can be concatenated back to a string. But if you start with a string "What are the first 10 Mersenne primes?" you don't really want to call the function What_are_the_first_10_Mersenne_primes, but rather something like firstMersenne(10). It's not an easy problem by any means![/QUOTE]

why not just Mersenne_Primes(n) ? the n would still have to be found later though.

[QUOTE=science_man_88;224918]why not just Mersenne_Primes(n) ? the n would still have to be found later though.[/QUOTE]

Either name would be fine. I'm just saying that you don't want a new function name for every English sentence -- there are too many valid sentences. (There are maybe half a million words in English. If you recognize 10,000 of those, and if only 1% of those are valid at a given point in the sentence, then there are 10^22 10-word sentences... writing one function per second, this would take 3 trillion lifetimes to finish.)

check modified post against vector of functions in database if it doesn't contain one of them or it still can't make sense of it all it's returns an error or questions respectively

[CODE]first_Mersenne_Primes(n)=Mersenne_Primes(n)[/CODE]?

that's the problem we need the code to make the problem into something it can understand before handing it the reins.

[QUOTE=3.14159;224909]Seeing as it works just fine for small numbers (I would rarely need it for large integers), it works for me![/QUOTE]

Really? I would expect it to be used only for reasonably large numbers. I've run it on all odd numbers below 10^10, for example, which is easily large enough to have trouble with roundoff.

well i showed how I'd break it down logically myself can we get the script to do the same.

[QUOTE=CRGreathouse]Really? I would expect it to be used only for reasonably large numbers. I've run it on all odd numbers below 10^10, for example, which is easily large enough to have trouble with roundoff.
[/QUOTE]

Yeah, it seems to work just fine with me, up until the 10[sup]30[/sup] range.

Also: Improved the precision.

For 1987021, there are ≈372006 bases which pass it as a pseudoprime.

@Sm88: Did you define what the Mersennes are? (Or at least Mersenne_Primes(n)?)

@CRG: I found the weakness in your program: It depends on factoring n.

What if n = something like 8929916458641913352287532945770212899164203997 * 4483710071772199066536995719064666355529706337783587 ?

Your program is rendered useless unless n is easily factored.

[QUOTE=3.14159;224923]Yeah, it seems to work just fine with me, up until the 10[sup]30[/sup] range.

Also: Improved the precision.[/QUOTE]

If it works for you up to 10^30 then your precision is set to at least, say, 30 decimal digits. :smile:

Again, I don't see the point in roundtripping: more time, possible precision errors.

[QUOTE=3.14159;224924]@CRG: I found the weakness in your program: It depends on factoring n.[/QUOTE]

Not really a weakness. The naive method requires n-1 modular exponentiations mod n, taking time [TEX]O(n\log^2n)[/TEX] or so. If Pari factored the numbers by trial division it would take time [TEX]O(\sqrt n)[/TEX] which is vastly better (~1000 trillion times better around 10^30 where you were just calculating). Of course Pari actually uses better methods, so it's faster yet.

Edit: You edited this following quote into your above post, so I'll edit in my reply.
[QUOTE=3.14159;224924]What if n = something like 8929916458641913352287532945770212899164203997 * 4483710071772199066536995719064666355529706337783587 ?[/QUOTE]

The naive method would test all ~4e97 bases. Each base would require the calculation of b^(n-1) mod n. These take about a millisecond each, for a total of ~4e94 seconds or ~1e85 lifetimes. Factoring n, if it wasn't written as above, could be done in a few hours. Big win for 'my' method.

[QUOTE=3.14159;224924]@Sm88: Did you define what the Mersennes are? (Or at least Mersenne_Primes(n)?)
[/QUOTE]
the code for it will figure it out so the best I can do right now(off the top of my head) is:

[CODE]a=0;for(p=1,x,if(isprime(p) && isprime(2^p-1),a=a+1;print(p);if(a==n,break();)) [/CODE]

but I haven't figured out how to do my method suggested earlier involving indexes of A002450 or A121290.

[QUOTE=CRGreathouse]The naive method would test all ~4e97 bases. Each base would require the calculation of b^(n-1) mod n. These take about a millisecond each, for a total of ~4e94 seconds or ~1e85 lifetimes. Factoring n, if it wasn't written as above, could be done in a few hours. Big win for 'my' method.
[/QUOTE]

Okay. But it would be rendered useless for any number larger than about 90-105 or so digits. I was right about it being unnecessary for larger integers.

Also: @Sm88: Isn't it supposed to be [code]a=0;for[B][COLOR="Red"]prime[/COLOR][/B](p=1,x,if(isprime(p) && isprime(2^p-1),a=a+1;print(p);if(a==n,break();))[/code] ?

(My emphasis in red.)

[QUOTE=3.14159;224929]
Also: @Sm88: Isn't it supposed to be [code]a=0;for[B][COLOR="Red"]prime[/COLOR][/B](p=1,x,if(isprime(p) && isprime(2^p-1),a=a+1;print(p);if(a==n,break();))[/code] ?[/QUOTE]

only if you know before hand x is under primelimit if it isn't forprime may not work as it uses primes[i] last I checked. so if you don't already have all the primes needed calculated it must calculate them on the fly and the isprime(p) would need to be eliminated if you use forprime as it's not needed until after exhausting primelimit.

[QUOTE=3.14159;224929]Okay. But it would be rendered useless for any number larger than about 90-105 or so digits. I was right about it being unnecessary for larger integers.[/QUOTE]

When I said larger integers, I meant integers larger than 2^32, since anything larger will cause problems at word precision for 32-bit computers. If you're using a 64-bit Linux system (the Windows version is 32-bit even on 64-bit computers) then the problem crops up above 2^64 or so. Since those ranges are quite factorable, it *is* relevant.

But even if you were concerned only about numbers below 2^32 ~ 4e9, I still wouldn't recommend using a complicated inelegant method.

[QUOTE=science_man_88;224930]only if you know before hand x is under primelimit if it isn't forprime may not work as it uses primes[i] last I checked. so if you don't already have all the primes needed calculated it must calculate them on the fly and the isprime(p) would need to be eliminated if you use forprime as it's not needed until after exhausting primelimit.[/QUOTE]

It uses the list of primes, yes. It doesn't call prime(i) which is actually pretty inefficient 'under the hood' as I recall.

And if you did use forprime, you wouldn't need to have isprime(p), just isprime(2^p-1).

[QUOTE=CRGreathouse;224932]It uses the list of primes, yes. It doesn't call prime(i) which is actually pretty inefficient 'under the hood' as I recall.

And if you did use forprime, you wouldn't need to have isprime(p), just isprime(2^p-1).[/QUOTE]

yes and if x> primelimit it would hand out :not enough primes precomputed or what ever it says. so if x>primelimit the isprime(p) is needed.

this is something the code creating script would have to figure out to give the most efficient codes.

An interesting aside:
[CODE]nu=valuation(f[1]-1,2);
for(i=2,#f,nu=min(nu,valuation(f[i]-1,2))[/CODE]
can be replaced by
[CODE]nu=valuation(f-vectorv(#f,X,1),2)[/CODE]

vectorv, because f is a column vector (and because PARI doesn't support vector/scalar addition).

[CODE](12:03) gp > nu=valuation(f-vectorv(#f,X,1),2)
*** _-_: forbidden addition t_POL + t_COL.[/CODE]

doesn't look like it.

and your first one came back syntax errors then I fixed it and :

[CODE](13:10) gp > for(i=2,#f,nu=min(nu,valuation(f[i]-1,2)))
*** for: _[_]: not a vector.[/CODE]

sorry forgot one thing.

[CODE](13:12) gp > nu=valuation(f[1]-1,2);for(i=2,#f,nu=min(nu,valuation(f[i]-1,2)))
*** _[_]: not a vector.[/CODE]

so

1)read(post)
2)dissect the post into parts we can search addhelp() with for a function that it will solve it
3) post it on the forum ?

Excellent.

A small inconvenience:

Here is a code snippet that allows me to search for 2nd kind Cunningham semiprimes (Of the form 2p[sup]2[/sup]-p that are pseudoprime to base 2):

[code]modbmpsp(x,n,m)=if(isPRP(modbm(x,n,m),b=2),print(modbm(x,n,m))[/code]

After it runs partially: Pari says:

[code]***Mod: division by zero.[/code]

Here is my PRP code:

[code]isPRP(n,b=2)={
my(s=valuation(n-1,2),d=n>>s);
n=Mod(b,n)^d;
if(n==1,return(1));
while(s--,
if(n==-1,return(1));
n=n^2
);
n==-1
};[/code]

Sorry for the question, but: Where is the code asking for a division by zero?

[QUOTE=3.14159;224940]Excellent.

A small inconvenience:

Here is a code snippet that allows me to search for 2nd kind Cunningham semiprimes (Of the form 2p[sup]2[/sup]-p that are pseudoprime to base 2):

[code]modbmpsp(x,n,m)=if(isPRP(modbm(x,n,m),b=2),print(modbm(x,n,m))[/code]

After it runs partially: Pari says:

[code]***Mod: division by zero.[/code]

Here is my PRP code:

[code]isPRP(n,b=2)={
my(s=valuation(n-1,2),d=n>>s);
n=Mod(b,n)^d;
if(n==1,return(1));
while(s--,
if(n==-1,return(1));
n=n^2
);
n==-1
};[/code]

Sorry for the question, but: Where is the code asking for a division by zero?[/QUOTE]

my guess is since n is not initiated, it is taken as 0 in which case I'm guessing Mod(b,n)^d comes to 0 but I'm unsure.

[QUOTE=3.14159;224940]A small inconvenience: [/QUOTE]
Definition of modbm?

Cute trick, axm. I didn't realize that valuation threaded over vectors, column or otherwise.

Pi, I'd need to see modbm to say. Also, modbmpsp doesn't have matched parentheses -- did you leave something off?

[QUOTE=CRGreathouse]Pi, I'd need to see modbm to say. Also, modbmpsp doesn't have matched parentheses -- did you leave something off?
[/QUOTE]

Here is modbm:

[code]modbm(x,n,m)=for(n=x,n,if(isprime(n*p(m)^2+1)&isprime(2*(n*p(m)^2+1)-1),print((n*p(m)^2+1)*(2*(n*p(m)^2+1)-1))));[/code]

NOTE: p(m) = p[sub]m[/sub]#

My normal looping function is normally b(m).

Well there's your problem. modbmpsp is expecting a return value and modbm doesn't give one, so modbmpsp treats the value as 0.

[QUOTE=CRGreathouse]Well there's your problem. modbmpsp is expecting a return value and modbm doesn't give one, so modbmpsp treats the value as 0.
[/QUOTE]

The code snippet for modbmpsp [B]does not ask for any return values.[/B]

If it were the PRP code that would be the problem:

It returns 1, which means there should be no issue.

[QUOTE=3.14159;224950]The code snippet for modbmpsp [B]does not ask for any return values.[/B][/QUOTE]

I've highlighted the part where a return value is expected.
[code]modbmpsp(x,n,m)=if(isPRP([COLOR="Red"]modbm(x,n,m)[/COLOR],b=2),print(modbm(x,n,m))[/code]

But modbm does not return anything, so the highlighted portion is treated as 0 by modbmpsp.

[QUOTE=3.14159;224950]If it were the PRP code that would be the problem:

It returns 1, which means there should be no issue.[/QUOTE]

I don't know what you mean by "it" here.

Ah, I see the issue now.. It merely copies modbm because there's some sort of error in the PRP command.

I have an idea: I will change the snippet to: if(isPRP(modbm(x,n,m),b=2)==1, ...

[QUOTE=3.14159;224953]Ah, I see the issue now.. It merely copies modbm because there's some sort of error in the PRP command.[/QUOTE]

If by "the PRP command" you mean the function isPRP, then no: this problem will occur regardless of how that function is written. If you mean something else, please specify.

[QUOTE=CRGreathouse]But modbm does not return anything, so the highlighted portion is treated as 0 by modbmpsp.
[/QUOTE]

Ah. Okay. I have it set to "print".

But it will only return that particular value.

I will set it as part of the loop of a function similar to modbm.

I will name it modbm2.

If you fix that, does it work? If so, great. If not, please post the modified code, seeing that both modbmpsp and modbm needed to be changed. (Edit: all the code, if you can -- p, modbm*, isPRP, and whatever else you're calling.)

Also, can you describe what these functions are supposed to do? Using addhelp is good practice, but any sort of description could help us follow what you're going for here.

[QUOTE=3.14159;224953]Ah, I see the issue now.. It merely copies modbm because there's some sort of error in the PRP command.

I have an idea: I will change the snippet to: if(isPRP(modbm(x,n,m),b=2)==1, ...[/QUOTE]

look to get a value out of a function and used by other functions if the first code returns nothing it is assumed to return 0 I think and so the value you are test as the first part of if (isprp() or what ever that part is is returning 0 since its variables are used later with no initial value they are assumed 0 and so mod by 0 error occurs. so to solve it the value outside of 0 of the other function so that other functions can use it.

[QUOTE=CRGreathouse]If you fix that, does it work? If so, great. If not, please post the modified code, seeing that both modbmpsp and modbm needed to be changed. (Edit: all the code, if you can -- p, modbm*, isPRP, and whatever else you're calling.)
[/QUOTE]

Here is the code snippet:
[code] modbm2(x,n,m)=for(n=x,n,if(isprime(n*p(m)^2+1)&isprime(2*(n*p(m^2)+1)-1)&isPRP((n*p(m)^2+1)*(2*(n*p(m)^2+1)-1)b=2),print((n*p(m)^2+1)*(2*(n*p(m)^2+1)-1))));[/code]

Now, it gives the expected returns. I saved that into the text file of all the defined functions.

[QUOTE=science_man_88;224957]look to get a value out of a function and used by other functions if the first code returns nothing it is assumed to return 0[/QUOTE]

Pretty much. Internally there are actually different values: the integer 0 (gen_0), positive and negative floating-point 0s at every precision level, and in this case a special value called gnil. When a function returns gnil the GUI knows to display nothing (and not increment the % number), but if a value is needed gnil is treated the same as gen_0.

[QUOTE=science_man_88;224957]so the value you are test as the first part of if (isprp() or what ever that part is is returning 0 since its variables are used later with no initial value they are assumed 0 and so mod by 0 error occurs. so to solve it the value outside of 0 of the other function so that other functions can use it.[/QUOTE]

That's not quite enough to cause the error, since it's the first part of a Mod() call -- we would be raising 0 to some power, which isn't division by zero unless the exponent is negative. And even that would give "impossible inverse mod X" rather than division by 0. But it was clearly a mistake, and getting one mistake out of the way may let us more clearly see what's actually wrong.

Of course the process of fixing that mistake may correct the other, who knows?

[QUOTE=3.14159;224958]Here is the code snippet:
[code] modbm2(x,n,m)=for(n=x,n,if(isprime(n*p(m)^2+1)&isprime(2*(n*p(m^2)+1)-1)&isPRP((n*p(m)^2+1)*(2*(n*p(m)^2+1)-1)b=2),print((n*p(m)^2+1)*(2*(n*p(m)^2+1)-1))));[/code]

Now, it gives the expected returns. I saved that into the text file of all the defined functions.[/QUOTE]

Glad to hear it.

[QUOTE=CRGreathouse]Glad to hear it.
[/QUOTE]

Now, using that function, I can modify the code to include as many bases as I'd like for it to be pseudoprime to.

[QUOTE=3.14159;224963]Now, using that function, I can modify the code to include as many bases as I'd like for it to be pseudoprime to.[/QUOTE]

I don't know what the goal of that or any of your functions are (well, other than isPRP which I presume checks if the input is a probable-prime. Wait, doesn't yours actually check if it's a strong probable prime instead?

[QUOTE=CRGreathouse]I don't know what the goal of that or any of your functions are (well, other than isPRP which I presume checks if the input is a probable-prime. Wait, doesn't yours actually check if it's a strong probable prime instead?
[/QUOTE]


*facepalm* isPRP is a strong pseudoprimality test and uses base 2. isWPRP is a Fermat test. isSPRP is a strong pseudoprimality test that performs trial factoring to nextprime(10[sup]6[/sup]) and uses a random base.

Carmichael numbers only pass isWPRP, not the other two, unless the Carmichael number happens to be a strong pseudoprime number to base 2. (Ex: 15841 is a Carmichael number and is a 2-SPRP.)

[QUOTE=3.14159;224967]*facepalm* isPRP is a strong pseudoprimality test.[/QUOTE]

I checked the code. The deceptively-named isPRP tests whether the input is a b-strong probable prime. A strong pseudoprimality test would be
[code]isSPSP(n,b)=isPRP(n,b)&!isprime(n)[/code]
a probable primality test would be
[code]isPRP_correct(n,b)=Mod(b,n)^(n-1)==1[/code]
and a pseudoprime test would be
[code]isPSP(n,b)=isPRP_correct(n,b)&&!isprime(n)[/code]

[QUOTE=CRGreathouse]I checked the code. The deceptively-named isPRP tests whether the input is a b-strong probable prime. A strong pseudoprimality test would be
[/QUOTE]

[B]So you're calling me a liar? Prove that I am a liar. [/B]

I suggest that you refresh before reply, as I was in the middle of refining the post, and retract the nonsense accusation.

[QUOTE=3.14159;224967]*facepalm* isPRP is a strong pseudoprimality test and uses base 2. isWPRP is a Fermat test. isSPRP is a strong pseudoprimality test that performs trial factoring to nextprime(10[sup]6[/sup]) and uses a random base.[/QUOTE]

Your function names bother me. The strong test doesn't have S in its name, etc. But at least document what they do in addhelp commands in your file so that when you share them people know that they do what they say, not what they're named.

[QUOTE=3.14159;224967]Carmichael numbers only pass isWPRP, not the other two, unless the Carmichael number happens to be a strong pseudoprime number to base 2. (Ex: 15841 is a Carmichael number and is a 2-SPRP.)[/QUOTE]

If you really want to be pedantic about it, Carmichael numbers don't always pass isWPRP -- they only pass it [TEX]\varphi(n)[/TEX] times, so 320 out of 560 times for 561. They can have lots of bad bases for the strong test, too -- but never more than a quarter. 8911 is a good example of a Carmichael number with lots of bad bases.

[QUOTE=3.14159;224969][B]So you're calling me a liar? Prove that I am a liar. [/B][/QUOTE]

I said that your functions were named deceptively. That statement stands.

I did not call you a liar, though I'd be happy to if you can point out an example of yourself lying.

[QUOTE=3.14159;224969]I suggest that you refresh before reply, as I was in the middle of refining the post, and retract the nonsense accusation.[/QUOTE]

Please refine your posts before posting.

[QUOTE=CRGreathouse]Your function names bother me. The strong test doesn't have S in its name, etc. But at least document what they do in addhelp commands in your file so that when you share them people know that they do what they say, not what they're named.
[/QUOTE]

[B]isSPRP[/B]? Isn't the meaning a bit self-evident there?

[QUOTE=CRGreathouse]But at least document what they do in addhelp commands in your file so that when you share them people know that they do what they say, not what they're named.[/QUOTE]

Done.

Glad to hear about the addhelp. It will, uh, help in the future.

[QUOTE=3.14159;224972][B]isSPRP[/B]? Isn't the meaning a bit self-evident there?[/QUOTE]

Your function isSPRP as described in post #270 is not the indicator function for the strong probable primes, as the name would suggest. Instead it is a probable-prime test incorporating the strong test and trial divison. Your function isPRP as listed in post #252 does not check if a number is a probable prime, as the name suggests, but instead checks if the number is a strong probable prime.

[QUOTE=CRGreathouse]Your function isSPRP as described in post #270 is not the indicator function for the strong probable primes, as the name would suggest. Instead it is a probable-prime test incorporating the strong test and trial divison. Your function isPRP as listed in post #252 does not check if a number is a probable prime, as the name suggests, but instead checks if the number is a strong probable prime.
[/QUOTE]

The help addition solves all. The name of the file I saved all the definitions of the functions to is named b(m).txt, and is indeed a text file.

[QUOTE=science_man_88;224913]so the basic idea I have of the process required is:

1)read for updates
2)send request to next part of script
3)find function names that can be understood in the text (if none exist give error and/or print questions the script has about the request)
4)print out code for functions if they are found to be in the database.
5) post code to Mersenne forums website.[/QUOTE]

instead of finding function names it's easier to find function descriptions(aka. addhelp()) in a post.

so for example if someone asks to find the first n Mersenne Numbers

in Mersenne(n) lets say the addhelp contains first n Mersenne Numbers

theres a match found it know that's the one it should print.

now they may use any variable so I wonder if we can say don't check for n check for anything in this position relative to the first part of this string. would this help to decipher? the hard part is we may need a lot of / or saying switch this synonyms addhelp from this term to this other set of them is there a way ?

[QUOTE=3.14159;224982]The help addition solves all. The name of the file I saved all the definitions of the functions to is named b(m).txt, and is indeed a text file.[/QUOTE]

Yep. I have at least one deceptive name amongst my functions: DickmanRho estimates, rather than computes, Dickman's rho.
[code]>?DickmanRho
Estimates the value of the Dickman rho function. For x <= 3 the exact values
are used, up to rounding; up to 15 the value is interpolated using known values
and rhoest; after 15 rhoest is used, along with a correction factor based on
the last value in rhoTable.

>?rhoest
de Bruijn's asymptotic approximation for rho(x), rewritten as in van de Lune
and Wattel 1969. Curiously, their paper shows values for this estimate that
differ from those calculated by this function, often as soon as the second
decimal place -- but as the difference is in the direction of the true value, I
have not looked further into this.[/code]

[QUOTE=science_man_88;224985]instead of finding function names it's easier to find function descriptions(aka. addhelp()) in a post.[/QUOTE]

Sure, but there are lots of ways to say things. You don't want the total size of your addhelp files to be 10^23 bytes, do you? :smile:

[QUOTE=science_man_88;224985]now they may use any variable so I wonder if we can say don't check for n check for anything in this position relative to the first part of this string. would this help to decipher? the hard part is we may need a lot of / or saying switch this synonyms addhelp from this term to this other set of them is there a way ?[/QUOTE]

It's a rather hard problem, and I do wish you luck. Synonym tables seem like a fair place to start.

Frankly, Perl would probably be better suited to this task than Pari -- Pari is bad at text processing, and that's where Perl shines.

how could you make a synoym table in pari ? I know for a function I do function1 = function2 but how do can i do it for addhelp technically it could be more than one help file if i can call more than one. how can I make a synonym table for changing one or 2 words in a addhelp if we go for short names.

There's no special way to do that. And given how painful string operations are in Pari, I wouldn't recommend doing them at all if you can avoid it.

[CODE]addhelp(fun,Vec(?foo) - "foo." + "fun.")[/CODE]

I tried something like that.

[CODE](18:38) gp > ?foo
a function called foo.[/CODE]

another thing I thought of can we use function1=function2 so it writes the function name without _ in each addhelp ?

If Perl is a way to do this then use it at least up to printing the functions have the Perl executable pass pari the function names to print out maybe or maybe the Perl program can read the script file(s) involved and print it to a command prompt. the point is it's useful. if a Perl expert can give us code similar to C maybe we can convert to Pari later on.

could we not make the read post into a vector of strings then sort from most important to least important according to a list/vector ?

oh by the way i found a typo in ?vecsort fonction-> function if I know what I'm talking about.

Random pseudoprime: 759932492170846988701 is pseudoprime to bases 2, 3, 5, 7, 11, and 13. By the way: Is there a world record for "largest composite pseudoprime"?

Also: I forgot how to write a Fermat pseudoprime generator.

[QUOTE=3.14159;225001]Random pseudoprime: 759932492170846988701 is pseudoprime to bases 2, 3, 5, 7, 11, and 13. By the way: Is there a world record for "largest composite pseudoprime"?[/QUOTE]

Not really, you can generate them essentially as large as you like.

[QUOTE=3.14159;225001]Also: I forgot how to write a Fermat pseudoprime generator.[/QUOTE]

Depends on what you mean by "generator". Are you looking for a program that does the Fermat test? A program that generates all Fermat pseudoprimes in a range? A program that generates a Fermat pseudoprime at a given size? Something else?

[QUOTE=CRGreathouse]Not really, you can generate them essentially as large as you like.
[/QUOTE]

I see.

[QUOTE=CRGreathouse]Depends on what you mean by "generator". Are you looking for a program that does the Fermat test? A program that generates all Fermat pseudoprimes in a range? A program that generates a Fermat pseudoprime at a given size? Something else?
[/QUOTE]

A program that generates the Fermat pseudoprimes in a given range, that are pseudoprime to user-selected bases. (No need for a code snippet, I eventually remembered how to write it and saved it in the text document, along with the other functions.

[TEX]24m= 6np+(p-7)\right m=px+c [/TEX]
[TEX] 24m=6np-(p+7)\right m=px+c ? [/TEX]
[TEX]if(px+c==(4n-1)/3,(4\strike n -1)/3[/TEX]
for all remaining n that create primes print(2*n+3) these are Mersenne prime exponents

get this CRG ?

An interesting application error:
Whenever I input 25326001, it returns that it is a 7-SPRP, when it is in fact reported "composite" using base 7. I verified that it was an error on the app. Now I see that this is an unreliable app, as it returns results that are clearly wrong.