Author Topic: PalPrime - Zeda  (Read 1981 times)

0 Members and 1 Guest are viewing this topic.

Offline Xeda112358

  • they/them
  • Moderator
  • LV12 Extreme Poster (Next: 5000)
  • ************
  • Posts: 4704
  • Rating: +719/-6
  • Calc-u-lator, do doo doo do do do.
    • View Profile
PalPrime - Zeda
« on: May 13, 2013, 08:43:21 pm »
So here is my palprime program, but after seeing Jim Bauwens' program and seeing that it could be tweaked to be much smaller and faster than mine, I don't know how much this is worth :P
Code: [Select]
Ans→N
0
If N<1 or fPart(N
Return
If N<6
Then
{2,3,5,7,11
Ans(N
Return
End
N-5→N
9→B
1→A
While N
B+1→B                       ;generate the next palindrome
If Ans=10A
Then
Ans→A
Else
If not(remainder(B,A
1+B+A(1+2(B=4A→B
End
B→C
.1Ans→D
While iPart(D
.1iPart(D→D
10(C+fPart(D→C
End                         ;palindrome is in C
If min(remainder(C,{3,7,11  ;Check primality
Then
√(C→D
{13,17,19,23,29,31,37,41
While max(Ans)≤D and min(remainder(C,Ans
Ans+30
End
N-not(not(min(remainder(C,Ans→N
End
End
C
For timings, I got 14 seconds for the 42nd prime palindrome, 58 seconds for the 100th, 494 seconds for the 290th.

Input is the 'nth' prime palindrome to return in Ans, and output is the nth prime palindrome (output in Ans).

Offline blue_bear_94

  • LV8 Addict (Next: 1000)
  • ********
  • Posts: 801
  • Rating: +25/-35
  • Touhou Enthusiast / Former Troll / 68k Programmer
    • View Profile
Re: PalPrime - Zeda
« Reply #1 on: May 13, 2013, 08:44:45 pm »
What algorithm did you use to compute the primes?
Due to dissatisfaction, I will be inactive on Omnimaga until further notice. (?? THP hasn't been much success and there's also the CE. I might possibly be here for a while.)
If you want to implore me to come back, or otherwise contact me, I can be found on GitHub (bluebear94), Twitter (@melranosF_), Reddit (/u/Fluffy8x), or e-mail (if you know my address). As a last resort, send me a PM on Cemetech (bluebear94) or join Touhou Prono (don't be fooled by the name). I've also enabled notifications for PMs on Omnimaga, but I don't advise using that since I might be banned.
Elvyna (Sunrise) 4 5%
TI-84+SE User (2.30 2.55 MP 2.43)
TI-89 Titanium User (3.10)
Casio Prizm User? (1.02)
Bag  東方ぷろの

Offline Xeda112358

  • they/them
  • Moderator
  • LV12 Extreme Poster (Next: 5000)
  • ************
  • Posts: 4704
  • Rating: +719/-6
  • Calc-u-lator, do doo doo do do do.
    • View Profile
Re: PalPrime - Zeda
« Reply #2 on: May 13, 2013, 08:51:41 pm »
Oh, it just uses a fairly simple trial division algorithm. I at one point uses a Fermat prime test modulo 2, but that algorithm is just too slow for anything smaller than 9 digits (in TI-BASIC it is, anyways). While it can return if a number is prime many times faster than trial division, it tends to be much slower than trial division at returning whether or not a number is composite (which is most numbers). So in the end, I found that it saved time to just remove the code for the Fermat test.

So instead, since all composite numbers except 2,3,5 are of the form 30k+{7,11,13,17,19,23,29,31}, I just check to see if any of those numbers are factors of the number up until the square root. The relevant code is:
Code: [Select]
If min(remainder(C,{3,7,11  ;Check primality
Then
√(C→D
{13,17,19,23,29,31,37,41
While max(Ans)≤D and min(remainder(C,Ans
Ans+30
End
N-not(not(min(remainder(C,Ans→N
End