Count in Prime Palindromes!

For all your silly time-killing forum games.

Moderators: jestingrabbit, Moderators General, Prelates

User avatar
kaimason1
WINNING
Posts: 298
Joined: Thu Oct 22, 2009 5:05 am UTC
Location: See avatar.

Re: Count in Prime Palindromes!

Postby kaimason1 » Mon Feb 15, 2010 4:56 pm UTC

76667
SexyTalon wrote:If it walks like a person, talks like a person, and tastes like a person, it's probably a person. Or I Can't Believe It's Not People, which cannibals prefer to Soylent Green nearly 5 to 1 in a blind taste test.

User avatar
Hiato
Posts: 13
Joined: Mon Nov 17, 2008 1:35 pm UTC
Location: Location, Location
Contact:

Re: Count in Prime Palindromes!

Postby Hiato » Sun Feb 21, 2010 11:09 am UTC

77377
The inequality of life: Nothing > Money

mx x = if head x == 0 then head (tail x) else mx (0:reverse (map head (groupBy (\x y -> x>y) (reverse x))))

User avatar
e^iπ+1=0
Much, much better than Gooder
Posts: 2065
Joined: Sun Feb 15, 2009 9:41 am UTC
Location: Lancaster

Re: Count in Prime Palindromes!

Postby e^iπ+1=0 » Sun Feb 21, 2010 11:12 am UTC

77477
poxic wrote:You, sir, have heroic hair.
poxic wrote:I note that the hair is not slowing down. It appears to have progressed from heroic to rocking.

(Avatar by Sungura)

User avatar
duckshirt
Posts: 567
Joined: Thu Feb 15, 2007 1:41 am UTC
Location: Pacific Northwest

Re: Count in Prime Palindromes!

Postby duckshirt » Wed Feb 24, 2010 11:56 am UTC

77977!
lol everything matters
-Ed

User avatar
She
Posts: 406
Joined: Fri Nov 28, 2008 8:08 pm UTC
Location: Sweden

Re: Count in Prime Palindromes!

Postby She » Wed Feb 24, 2010 8:00 pm UTC

That's not true though - I don't know about it being palindrome, it might be, but it's not prime. Some of its factors include 2, 3, 4... 77976 and 77977.
She speaks in the third person
So she can forget that she's me

User avatar
BurningLed
Posts: 561
Joined: Tue Feb 09, 2010 5:42 pm UTC

Re: Count in Prime Palindromes!

Postby BurningLed » Wed Feb 24, 2010 10:20 pm UTC

93139
Axman wrote:Some people blow their cash on watches that they show off to people who think said watches make a person cool. Some people spend a weekend buying everyone fake gifts in a game of make-believe.
I think the latter group is awesome.

User avatar
Hiato
Posts: 13
Joined: Mon Nov 17, 2008 1:35 pm UTC
Location: Location, Location
Contact:

Re: Count in Prime Palindromes!

Postby Hiato » Thu Feb 25, 2010 5:22 pm UTC

duckshirt wrote:77977!

She wrote:That's not true though - I don't know about it being palindrome, it might be, but it's not prime. Some of its factors include 2, 3, 4... 77976 and 77977.

I sincerely doubt he meant the factorial of seventy-seven thousand nine-hundred and seventy-seven so much as 77977 I can haz big prym! (wat iz same furwerd nd bakwud)

BurningLed wrote:93139


I believe that after 77977 come 78487, 78787, 78887, 79397, 79697, 79997, 90709, 91019 and then 93139. But I don't believe we have a defined interval (naturally, as will be true for primes) so I'll just go with 93239
The inequality of life: Nothing > Money

mx x = if head x == 0 then head (tail x) else mx (0:reverse (map head (groupBy (\x y -> x>y) (reverse x))))

User avatar
Max2009
Posts: 160
Joined: Mon Mar 09, 2009 2:20 pm UTC
Location: Where?
Contact:

Re: Count in Prime Palindromes!

Postby Max2009 » Thu Feb 25, 2010 9:42 pm UTC

93339
Wow! This thread has been resurrected!
Also, I piped my code to an outfile, and now my lookup time is O(1). Not even amortized O(1). Just plain O(1).
Cogito ergo surf - I think therefore I network

Registered Linux user #481826 Get Counted! http://counter.li.org

Image

User avatar
Hiato
Posts: 13
Joined: Mon Nov 17, 2008 1:35 pm UTC
Location: Location, Location
Contact:

Re: Count in Prime Palindromes!

Postby Hiato » Sun Feb 28, 2010 2:18 pm UTC

Max2009 wrote:93339
Wow! This thread has been resurrected!
Also, I piped my code to an outfile, and now my lookup time is O(1). Not even amortized O(1). Just plain O(1).


Just out of interest, although a palindrome, how does 93339 avoid being a multiple of three? :) Anyway, 93739
The inequality of life: Nothing > Money

mx x = if head x == 0 then head (tail x) else mx (0:reverse (map head (groupBy (\x y -> x>y) (reverse x))))

User avatar
Max2009
Posts: 160
Joined: Mon Mar 09, 2009 2:20 pm UTC
Location: Where?
Contact:

Re: Count in Prime Palindromes!

Postby Max2009 » Sun Feb 28, 2010 8:52 pm UTC

94049

Let this be a lesson to you youngsters: give your subclasses meaningful names.
In an attempt to be efficient and to write modular code I wrote a separate class to find palindromes, and a separate class to find prime numbers, and a third class to just instantiate the other two and run them, one after the other. (I know it's not efficient, but it's modular as hell.)
Having not looked at the code in several months, I forgot who did what, and just ran a class at random.
Clearly it was the palindrome class, not the primes.
Cogito ergo surf - I think therefore I network

Registered Linux user #481826 Get Counted! http://counter.li.org

Image

wilywes
Posts: 11
Joined: Tue Sep 29, 2009 7:17 pm UTC

Re: Count in Prime Palindromes!

Postby wilywes » Wed Mar 03, 2010 6:12 pm UTC

94349

So I learned that short and neat is not always better than complicated and powerful. The efficiency of the language also helps. After seeing this thread's revival, I was inspired to rewrite my python code into C++. Piping the same inputs to python's source code and C++ source code took 20.02 seconds and 1.84 seconds, respectively, to calculate palindromic primes up to 10,000,000.

User avatar
Max2009
Posts: 160
Joined: Mon Mar 09, 2009 2:20 pm UTC
Location: Where?
Contact:

Re: Count in Prime Palindromes!

Postby Max2009 » Wed Mar 03, 2010 7:36 pm UTC

94649

I'm impressed with my code all over again. I ran it to 10,000,000 in 1680 milliseconds.
Cogito ergo surf - I think therefore I network

Registered Linux user #481826 Get Counted! http://counter.li.org

Image

User avatar
e^iπ+1=0
Much, much better than Gooder
Posts: 2065
Joined: Sun Feb 15, 2009 9:41 am UTC
Location: Lancaster

Re: Count in Prime Palindromes!

Postby e^iπ+1=0 » Thu Mar 04, 2010 1:15 am UTC

94849

Nice. Mine takes about 12 seconds to run to 10,000,000. Then again, I'm also using python.
poxic wrote:You, sir, have heroic hair.
poxic wrote:I note that the hair is not slowing down. It appears to have progressed from heroic to rocking.

(Avatar by Sungura)

User avatar
Sc4Freak
Posts: 673
Joined: Thu Jul 12, 2007 4:50 am UTC
Location: Redmond, Washington

Re: Count in Prime Palindromes!

Postby Sc4Freak » Thu Mar 04, 2010 9:05 pm UTC

94949

Talking about speed, this is why I love C++.

Spoiler:

Code: Select all

#include <iostream>
#include <ctime>
#include <fstream>
#include <boost/cstdint.hpp>
#include <boost/lexical_cast.hpp>

using boost::uint64_t;

#ifdef _MSC_VER
#define INLINE __forceinline
#else
#define INLINE inline
#endif

template<uint64_t Base>
class PowTable
{
public:
    PowTable()
    {
        uint64_t x = 1;
        for(int i = 0; i < 64; ++i) {
            values[i] = x;
            x *= Base; // who cares about overflow
        }
    }

    INLINE uint64_t operator()(uint64_t power) const {
        return values[power];
    }

private:
    uint64_t values[64]; // max 64 entries for a 64-bit integer
};

static const PowTable<10> Pow10;

INLINE uint64_t CountDigits(uint64_t x)
{
    uint64_t i = 0;
    while(x != 0)
    {
        x /= 10;
        ++i;
    }
    return i;
}

class PalindromeGenerator
{
public:
    PalindromeGenerator() : key(1), oddDigitCount(false)
    {}

    INLINE uint64_t Next()
    {
        uint64_t numDigits = CountDigits(key);
        uint64_t numDigitsOrig = numDigits;
        if(oddDigitCount)
            --numDigits;
        uint64_t first = key * Pow10(numDigits);

        // Build second by reversing the digits of key
        uint64_t second = 0;
        if(oddDigitCount)
        {
            for(uint64_t i = 0; i < numDigits; ++i)
            {
                uint64_t digit = key / Pow10(i + 1) % 10;
                second += digit * Pow10(numDigits - i - 1);
            }
        }
        else
        {
            for(uint64_t i = 0; i < numDigits; ++i)
            {
                uint64_t digit = key / Pow10(i) % 10;
                second += digit * Pow10(numDigits - i - 1);
            }
        }

        if(key == Pow10(numDigitsOrig) - 1)
        {
            if(oddDigitCount)
                key /= 10;
            oddDigitCount = !oddDigitCount;
        }
        ++key;

        return (first + second);
    }

    void Reset()
    {
        key = 1;
    }

private:
    uint64_t key;

    // determines whether to produce a palindrome with an odd number of digits
    bool oddDigitCount;
};

INLINE bool IsFactor(uint64_t num, uint64_t divisor)
{
    return (num % divisor == 0);
}

INLINE bool IsPrime(uint64_t num)
{
    if(num == 2)
        return true;
    if(IsFactor(num, 2))
        return false;
    for(uint64_t i = 3; i * i <= num; i += 2)
    {
        if(IsFactor(num, i))
            return false;
    }
    return true;
}

int main(int argc, char** argv)
{
    using namespace std;

    if(argc < 2)
    {
        std::cout << "Specify number to generate prime palindromes to." << std::endl;
        return 0;
    }

    PalindromeGenerator palindromeGenerator;
    uint64_t maxVal = boost::lexical_cast<uint64_t>(argv[1]);

    std::fstream file("out.txt", std::fstream::out | std::fstream::trunc);

    clock_t startTime = clock();
    while(true)
    {
        uint64_t i = palindromeGenerator.Next();
        if(i > maxVal)
        {
            cout << "Time taken: " << (clock() - startTime) * 1000 / CLOCKS_PER_SEC << "ms" << endl;
            return 0;
        }
        if(IsPrime(i))
        {
            file << i << std::endl;
        }
    }
}
Generates prime palindromes up to 10,000,000 in < 15ms on my 2.4Ghz Core 2 Duo laptop. I don't know the exact running time because the timer resolution is only 15ms on Windows.

User avatar
Max2009
Posts: 160
Joined: Mon Mar 09, 2009 2:20 pm UTC
Location: Where?
Contact:

Re: Count in Prime Palindromes!

Postby Max2009 » Fri Mar 05, 2010 7:44 am UTC

95959

Nice code. Too bad about the Windows fail. Maybe when I have the time and patience I'll run it on my 2.4Ghz Centrino Duo 1 GB RAM laptop running Linux and we'll get a better resolution.
Be aware though that I'll be using the Gnu C Compiler, so the time might be a little different.
Cogito ergo surf - I think therefore I network

Registered Linux user #481826 Get Counted! http://counter.li.org

Image

User avatar
Lorenz
Posts: 27
Joined: Fri Apr 29, 2011 5:57 am UTC

Re: Count in Prime Palindromes!

Postby Lorenz » Mon Oct 10, 2011 3:38 am UTC

96269

awesome thread btw

User avatar
Max2009
Posts: 160
Joined: Mon Mar 09, 2009 2:20 pm UTC
Location: Where?
Contact:

Re: Count in Prime Palindromes!

Postby Max2009 » Tue Oct 11, 2011 9:03 am UTC

Hurray for the necro!

96469
Cogito ergo surf - I think therefore I network

Registered Linux user #481826 Get Counted! http://counter.li.org

Image

User avatar
Lorenz
Posts: 27
Joined: Fri Apr 29, 2011 5:57 am UTC

Re: Count in Prime Palindromes!

Postby Lorenz » Tue Oct 11, 2011 1:37 pm UTC

96769

Also, I'm using mathematica. I'll probably switch over to python or C soon.

User avatar
Sean Quixote
Posts: 229
Joined: Tue Sep 14, 2010 1:20 am UTC
Location: Ubeki-beki-beki-beki-stan-stan

Re: Count in Prime Palindromes!

Postby Sean Quixote » Tue Oct 11, 2011 10:53 pm UTC

97379

I was going to google a prime calculator or something, but then I remembered that I have the first 50 million primes saved on my computer... :shock:

User avatar
Lorenz
Posts: 27
Joined: Fri Apr 29, 2011 5:57 am UTC

Re: Count in Prime Palindromes!

Postby Lorenz » Fri Oct 14, 2011 1:30 pm UTC

97579

User avatar
Sean Quixote
Posts: 229
Joined: Tue Sep 14, 2010 1:20 am UTC
Location: Ubeki-beki-beki-beki-stan-stan

Re: Count in Prime Palindromes!

Postby Sean Quixote » Mon Oct 17, 2011 2:53 am UTC

97879

tomtom2357
Posts: 563
Joined: Tue Jul 27, 2010 8:48 am UTC

Re: Count in Prime Palindromes!

Postby tomtom2357 » Mon Jan 02, 2012 10:12 am UTC

98389
I have discovered a truly marvelous proof of this, which this margin is too narrow to contain.

tomtom2357
Posts: 563
Joined: Tue Jul 27, 2010 8:48 am UTC

Re: Count in Prime Palindromes!

Postby tomtom2357 » Sat Jan 07, 2012 3:07 am UTC

98689, nobody said anything about double posting.
I have discovered a truly marvelous proof of this, which this margin is too narrow to contain.

tomtom2357
Posts: 563
Joined: Tue Jul 27, 2010 8:48 am UTC

Re: Count in Prime Palindromes!

Postby tomtom2357 » Sat Jan 07, 2012 4:36 pm UTC

1003001 or triple posting, how about this, if no one has posted in the last 12 hours, then you can double post (or triple post etc) to keep the thread going.

Edit: Actually, we just reached a million, so I'll stop now. :(
I have discovered a truly marvelous proof of this, which this margin is too narrow to contain.

User avatar
XTCamus
Posts: 176
Joined: Fri Sep 02, 2011 11:59 pm UTC
Location: "...on that dizzying crest"

Re: Count in Prime Palindromes!

Postby XTCamus » Tue Oct 30, 2012 9:16 pm UTC

Isn't anyone else surprised that there were no six figure prime palindromes? And, if I'm not mistaken, this is because every six figure palindrome is evenly divisible by eleven....?

Also, where did it say the count was only going to a million, huh? Why not a billion?

P.s. These are a bitch to find using just Excel, so...... I got nothing.

User avatar
Vytron
Posts: 432
Joined: Mon Oct 19, 2009 10:11 am UTC
Location: The Outside. I use She/He/Her/His/Him as gender neutral pronouns :P

Re: Count in Prime Palindromes!

Postby Vytron » Thu Nov 01, 2012 4:52 am UTC

Yeah huh, there's no way I'm going to check manually if the next prime is a palindrome, or check all the following primes until I found the next palindrome, or check the next palindromes until I find a prime. It's much easier to just cheat:

1008001
Go! Go! You can do it username5243!
Cheers Marsh'n!

Your ad here. No, seriously! It's free! PM me if interested.
THANKS KARHELL!! :)

User avatar
Sean Quixote
Posts: 229
Joined: Tue Sep 14, 2010 1:20 am UTC
Location: Ubeki-beki-beki-beki-stan-stan

Re: Count in Prime Palindromes!

Postby Sean Quixote » Tue Feb 19, 2013 7:05 am UTC

1022201


Return to “Forum Games”

Who is online

Users browsing this forum: No registered users and 36 guests