A Late Night Conversation

Computer Science Level 5

Two years ago, we were up talking at about One.

She: Why aren't you replying for last two minutes?

Me: My computer just stopped responding.

She: Isn't that just an excuse to not talk to me?

Me: No, dear. I just calculated that <LargePrimeX> + <LargePrimeY> = <YourPhoneNumber> where <LargePrimeX> and <LargePrimeY> are prime numbers.

She: You do all these up so late?

Me: Yup...

She: Had it been any other girl, she'd have gone mad. Only because it's me, I've been in sound mental health for so long!

I recently realised that the last four digits of her phone number can be expressed as a sum of two primes in 103 ways.

What is the maximum possible value of the last four digits of her phone number?

Details and Assumptions:

PrimeA + PrimeB and PrimeB + PrimeA are counted as the same solution.
The primes need not be distinct.
22 can be written as a sum of two primes in three ways.

The answer is 9986.

2 solutions

Agnishom Chattopadhyay
Feb 10, 2015

Sage Code:

def goldbachp(num):
    l1 = []
    l2 = []
    for p1 in Primes():
        p2 = num - p1
        if p2 in Primes():
            if l1 and (p2 == l1[len(l1)-1] or p2 == l1[len(l1)-2]):
                break
            l1.append(p1)
            l2.append(p2)
    return l1,l2

Now, as Azhaghu suggested, start backwards from 9999 until you get len(goldbachp(n)[0])=103

for i1 in xrange(9262,0,-1):
   if len(goldbachp(i1)[0])=103:
      print i1
      break

#include<iostream.h>
#include<conio.h>
#include<math.h>

int isprime(long p)
    {
    int r=1;
    for(long i=2;i<=sqrt(p);i++)
        if(p%i==0)
            {r=0;break;}
    return r;
    }

int main()
    {
    clrscr();
    for(long i=1000,x=0;i<=9999;x=0,i+=2)
        {
        for(long j=3;j<=(i/2);j+=2)
            if(isprime(j)&&isprime(i-j))
                x++;
        if(x==103)
            cout<<i<<endl;
        }
    getch();
    return 0;
    }

Raghav Vaidyanathan - 6 years, 2 months ago

Vladimir Lem
Mar 6, 2015

let $x$ and $y$ be a prime number, and N be the last four digits of her phone number. Then we can write this:

$x + y$ = $N$ where $0001\le N\le 9999$ .

Since we know prime numbers are positive, we can safely assume that $x,y\le 9999$ . We can use this assumption to find all possible values of $N$ by generating all possible values of $x,y$ with Sieve of Eratosthenes.

My C++ code:

#include <bits/stdc++.h>
using namespace std;
bool prime[10000];
int sumof[10000];
int i,j,k;
vector <int> primes;

int main() {
    for (i=0;i<10000;i++) { prime[i]=true; sumof[i] = 0;}

    // Sieve of Eratosthenes
    for (i=2;i<10000;i++) {
        if (prime[i]) {
            primes.push_back(i);
            for (j=i*i;j<10000;j+=i) prime[j]=false;
        }
    }
    for (i=0;i<primes.size();i++)
        for (j=i;j<primes.size();j++) {
            if (primes[i]+primes[j] > 9999) break; 
            else {
                sumof[primes[i]+primes[j]]++; 
            }
        }
    for (k=9999;k>=0;k--) if (sumof[k] == 103) break; 
    cout << k << endl;
    return 0;
}

Output: 9986

A Late Night Conversation

The answer is 9986.

2 solutions

0 pending reports