mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Puzzles

Reply
 
Thread Tools
Old 2022-01-17, 21:12   #23
SmartMersenne
 
Sep 2017

8316 Posts
Default

Quote:
Originally Posted by dg211 View Post
I get the same answers for n = 9, d = 7 and n = 10, d = 8. It is possible to do it with a lot less computation - my single threaded C++ code took about 3.5s for n = 9, d = 7 and about 32s for n = 10, d = 8. Almost all of the time for n = 10 (like 31.9s) was spent generating a list of 8 digit primes.
Maybe you can post your solution next month (after the solution is posted on IBM site).
SmartMersenne is offline   Reply With Quote
Old 2022-01-18, 11:04   #24
dg211
 
Jun 2016

17 Posts
Default

Sure, can do.

Quote:
Originally Posted by SmartMersenne View Post
Maybe you can post your solution next month (after the solution is posted on IBM site).
dg211 is offline   Reply With Quote
Old 2022-02-13, 12:00   #25
dg211
 
Jun 2016

17 Posts
Default

The solution is up on the IBM site now, so sharing my code as SmartMersenne suggested.

The key observations I used to make it reasonably fast were:
- You can rotate the whole circle without affecting the score so e.g. 2345671 is equivalent to 1234567. That means for any set of n digits you can pick an arbitrary one to be first in the circle, and only look at (n-1)! arrangements rather than n!
- Rearranging the digits in the circle doesn't affect the primes you can make, only the score. And you can count how many times each digit follows each other digit in the list of primes that are makeable. So for example 32467 contributes one instance of a 3 followed by a 2, one 2 followed by 4, etc. Then when you rearrange the digits, you just need to calculate how much score a 3 followed by a 2 will contribute for that arrangement and add that to the score for each instance of 3 followed by 2 in the set of makeable primes, and so on. That means you don't have to completely start from scratch for a circle like 3762451 if you have already computed the score for the circle 1234567.

My GetPrimes function is not very efficient and was the bottleneck for n = 10 by miles. I did write another one which was a lot better (about 1s for n = 10) but I'm sure it's possible to do better still.

Code:
#include <vector>
#include <intrin.h>
#include <algorithm>
#include <chrono>

std::vector<uint64_t> GetPrimes(uint64_t n)
{
    std::vector<uint64_t> primes = {2};
    for (uint64_t i = 3; i < n; i+=2)
    {
        bool isPrime = true;
        for (auto p : primes)
        {
            if (i % p == 0)
            {
                isPrime = false;
                break;
            }
            if (p * p > i)
            {
                break;
            }
        }
        if (isPrime)
        {
            primes.push_back(i);
        }
    }

    return primes;
}

int main()
{
    int n = 8;
    int d = 6;

    auto startTime = std::chrono::steady_clock::now();
    uint64_t powersOfTen[11];
    powersOfTen[0] = 1i64;
    for (int i = 1; i < 11; i++)
    {
        powersOfTen[i] = powersOfTen[i - 1] * 10i64;
    }
    std::vector<int> digits;
    digits.resize(n);

    auto primes = GetPrimes(powersOfTen[d]);

    printf("t = %llu ms\n", std::chrono::duration_cast<std::chrono::milliseconds>(std::chrono::steady_clock::now() - startTime).count());

    std::vector<uint64_t> allowedPrimes;
    for (auto p : primes)
    {
        if (p >= powersOfTen[d - 1] && p < powersOfTen[d])
        {
            // check the digits are distinct
            int digitCount[10] = {0};
            bool digitsDistinct = true;
            uint64_t t = p;
            while (t > 0)
            {
                digitCount[t % 10] += 1;
                if (digitCount[t % 10] > 1)
                {
                    digitsDistinct = false;
                }
                t /= 10;
            }
            if (digitsDistinct)
            {
                allowedPrimes.push_back(p);
            }
        }
    }

    uint64_t maxScore = 0;
    uint64_t minScore = 1 << 30;

    std::vector<int> minScoreDigits;
    std::vector<int> maxScoreDigits;

    for (int i = 0; i < (1 << 10); i++)
    {
        if (__popcnt(i) == n)
        {
            int k = 0;
            for (int j = 0; j < 10; j++)
            {
                if (i & (1 << j))
                {
                    digits[k++] = j;
                }
            }

            uint64_t digitTransitions[10][10];
            memset(digitTransitions, 0, 100 * sizeof(uint64_t));

            for (auto p : allowedPrimes)
            {
                bool canMakePrime = true;
                uint64_t t = p;
                while (t > 0)
                {
                    int m = 1 << (t % 10);
                    if ((m & i) == 0)
                    {
                        canMakePrime = false;
                    }
                    t /= 10;
                }
                if (canMakePrime)
                {
                    uint64_t t = p;
                    int lastDigit = t % 10;
                    t /= 10;
                    while (t > 0)
                    {
                        digitTransitions[t % 10][lastDigit] += 1;
                        lastDigit = t % 10;
                        t /= 10;
                    }
                }
            }

            do
            {
                uint64_t score = 0;
                int digitPositions[10] = {0};
                int j = 0;
                for (auto d : digits)
                {
                    digitPositions[d] = j++;
                }
                for (int j = 0; j < 10; j++)
                {
                    for (int k = 0; k < 10; k++)
                    {
                        if (digitTransitions[j][k] > 0)
                        {
                            int digitDistance = (digitPositions[j] + n - digitPositions[k]) % n;
                            digitDistance = std::min(digitDistance, n - digitDistance);
                            score += digitTransitions[j][k] * digitDistance;
                        }
                    }
                }
                if (score < minScore)
                {
                    minScore = score;
                    minScoreDigits = digits;
                }
                if (score > maxScore)
                {
                    maxScore = score;
                    maxScoreDigits = digits;
                }
            } while (std::next_permutation(digits.begin() + 1, digits.end()));
        }
    }

    for (auto d : minScoreDigits)
    {
        printf("%i", d);
    }
    printf(", %lli\n", minScore);

    for (auto d : maxScoreDigits)
    {
        printf("%i", d);
    }
    printf(", %lli\n", maxScore);

    printf("t = %llu ms", std::chrono::duration_cast<std::chrono::milliseconds>(std::chrono::steady_clock::now() - startTime).count());

    return 0;
}
dg211 is offline   Reply With Quote
Old 2022-02-14, 01:08   #26
Yusuf
 
Jan 2020

11 Posts
Default

Quote:
Originally Posted by dg211 View Post
The solution is up on the IBM site now, so sharing my code as SmartMersenne suggested.

The key observations I used to make it reasonably fast were:
- You can rotate the whole circle without affecting the score so e.g. 2345671 is equivalent to 1234567. That means for any set of n digits you can pick an arbitrary one to be first in the circle, and only look at (n-1)! arrangements rather than n!
- Rearranging the digits in the circle doesn't affect the primes you can make, only the score. And you can count how many times each digit follows each other digit in the list of primes that are makeable. So for example 32467 contributes one instance of a 3 followed by a 2, one 2 followed by 4, etc. Then when you rearrange the digits, you just need to calculate how much score a 3 followed by a 2 will contribute for that arrangement and add that to the score for each instance of 3 followed by 2 in the set of makeable primes, and so on. That means you don't have to completely start from scratch for a circle like 3762451 if you have already computed the score for the circle 1234567.

My GetPrimes function is not very efficient and was the bottleneck for n = 10 by miles. I did write another one which was a lot better (about 1s for n = 10) but I'm sure it's possible to do better still.

Code:
#include <vector>
#include <intrin.h>
#include <algorithm>
#include <chrono>

std::vector<uint64_t> GetPrimes(uint64_t n)
{
    std::vector<uint64_t> primes = {2};
    for (uint64_t i = 3; i < n; i+=2)
    {
        bool isPrime = true;
        for (auto p : primes)
        {
            if (i % p == 0)
            {
                isPrime = false;
                break;
            }
            if (p * p > i)
            {
                break;
            }
        }
        if (isPrime)
        {
            primes.push_back(i);
        }
    }

    return primes;
}

int main()
{
    int n = 8;
    int d = 6;

    auto startTime = std::chrono::steady_clock::now();
    uint64_t powersOfTen[11];
    powersOfTen[0] = 1i64;
    for (int i = 1; i < 11; i++)
    {
        powersOfTen[i] = powersOfTen[i - 1] * 10i64;
    }
    std::vector<int> digits;
    digits.resize(n);

    auto primes = GetPrimes(powersOfTen[d]);

    printf("t = %llu ms\n", std::chrono::duration_cast<std::chrono::milliseconds>(std::chrono::steady_clock::now() - startTime).count());

    std::vector<uint64_t> allowedPrimes;
    for (auto p : primes)
    {
        if (p >= powersOfTen[d - 1] && p < powersOfTen[d])
        {
            // check the digits are distinct
            int digitCount[10] = {0};
            bool digitsDistinct = true;
            uint64_t t = p;
            while (t > 0)
            {
                digitCount[t % 10] += 1;
                if (digitCount[t % 10] > 1)
                {
                    digitsDistinct = false;
                }
                t /= 10;
            }
            if (digitsDistinct)
            {
                allowedPrimes.push_back(p);
            }
        }
    }

    uint64_t maxScore = 0;
    uint64_t minScore = 1 << 30;

    std::vector<int> minScoreDigits;
    std::vector<int> maxScoreDigits;

    for (int i = 0; i < (1 << 10); i++)
    {
        if (__popcnt(i) == n)
        {
            int k = 0;
            for (int j = 0; j < 10; j++)
            {
                if (i & (1 << j))
                {
                    digits[k++] = j;
                }
            }

            uint64_t digitTransitions[10][10];
            memset(digitTransitions, 0, 100 * sizeof(uint64_t));

            for (auto p : allowedPrimes)
            {
                bool canMakePrime = true;
                uint64_t t = p;
                while (t > 0)
                {
                    int m = 1 << (t % 10);
                    if ((m & i) == 0)
                    {
                        canMakePrime = false;
                    }
                    t /= 10;
                }
                if (canMakePrime)
                {
                    uint64_t t = p;
                    int lastDigit = t % 10;
                    t /= 10;
                    while (t > 0)
                    {
                        digitTransitions[t % 10][lastDigit] += 1;
                        lastDigit = t % 10;
                        t /= 10;
                    }
                }
            }

            do
            {
                uint64_t score = 0;
                int digitPositions[10] = {0};
                int j = 0;
                for (auto d : digits)
                {
                    digitPositions[d] = j++;
                }
                for (int j = 0; j < 10; j++)
                {
                    for (int k = 0; k < 10; k++)
                    {
                        if (digitTransitions[j][k] > 0)
                        {
                            int digitDistance = (digitPositions[j] + n - digitPositions[k]) % n;
                            digitDistance = std::min(digitDistance, n - digitDistance);
                            score += digitTransitions[j][k] * digitDistance;
                        }
                    }
                }
                if (score < minScore)
                {
                    minScore = score;
                    minScoreDigits = digits;
                }
                if (score > maxScore)
                {
                    maxScore = score;
                    maxScoreDigits = digits;
                }
            } while (std::next_permutation(digits.begin() + 1, digits.end()));
        }
    }

    for (auto d : minScoreDigits)
    {
        printf("%i", d);
    }
    printf(", %lli\n", minScore);

    for (auto d : maxScoreDigits)
    {
        printf("%i", d);
    }
    printf(", %lli\n", maxScore);

    printf("t = %llu ms", std::chrono::duration_cast<std::chrono::milliseconds>(std::chrono::steady_clock::now() - startTime).count());

    return 0;
}
I had a similar approach but programmed in Java.
I found that the set of all non-equivalent circles are formally called a "necklace".
Since the elements of the circles are always unique, I was able to generate necklaces of a length N circle by first generating all permutations of the first N-1 digits and adjoining the Nth element to the end of every permutation I generated, which matches the (N-1)! number of arrangements you mentioned.
Yusuf is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
2022 project goals gd_barnes Conjectures 'R Us 3 2022-05-26 08:59
2022 Project Goal discussion rogue Conjectures 'R Us 15 2021-12-19 21:20

All times are UTC. The time now is 10:53.


Sat May 28 10:53:05 UTC 2022 up 44 days, 8:54, 0 users, load averages: 1.35, 1.28, 1.33

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔