Herhangi Matematiksel Şeyler: Euler Projesi 278. Soru

Yarı Asalların Lineer Kombinasyonları

$1<a_1<a_2<...<a_n$ tamsayıları için, sadece $q_k\ge 0$ tamsayı değerleri kullanılarak elde edilen $q_1a_1+q_2a_2+...+q_na_n=b$ lineer kombinasyonunu ele alalım.

Belirli bir $a_k$ kümesi için her $b$ değerinin mümkün olmayabileceğine dikkat edin. Örneğin $a_1=5, a_2=7$ için $b=1,2,3,4,6,8,9,11,13,16,18,23$ değerlerini veren $q_1\ge 0$ ve $q_2\ge 0$ değerleri bulunmamaktadır. Görüldüğü üzere bu koşullarda en büyük imkansız $b$ değeri 23'tür. Bunu $f(5,7)=23$ ile gösterelim.

Benzer şekilde $f(6,10,15)=29$ ve $f(14,22,77)=195$ olacağı gösterilebilir.

$p<q<r<5000$ asalları için $\sum f(pq,pr,qr)$ değeri kaçtır?
Cevap:
1228215747273908452

Python:
t=0
   ps=makeprimes(N)
   C=[]
   for p in ps:
      t+=p
      C.append(t)
   t=0
   for j in xrange(1,len(ps)-1):
      q=ps[j]
      t+=(2*q-1)*C[j-1]*(C[-1]-C[j])-q*(C[-1]-C[j])*j-q*(C[j-1])*(len(ps)-j-1)
   print t

C/C++:
#include <stdio.h>

#define N 5000
long long int answer = 0;

int prime_search[N];
int prime_t[N];
int primen=0;

void make_primetable();

int main(int argc, char **argv) {
  int i, j, k;
  long long int s,t;
  make_primetable();

for (i=0; i<primen-2; i++)
    for (j=i+1; j<primen-1; j++)
      for (k=j+1; k<primen; k++) {
 s = ((long long int)prime_t[k]*prime_t[j]-prime_t[k]-prime_t[j])*(long long int)prime_t[i];
 t = prime_t[k]*prime_t[j];
 answer += s+t*(prime_t[i]-1);
      }

printf ("answer: %lld\n", answer);
}

void make_primetable() {
   ... snipped ...
}

Haskell:
import ONeillPrimes (primesToLimit)

main :: IO ()
main = print.sum $ do
  p <- ps
  q <- dropWhile (<= p) ps
  r <- dropWhile (<= q) ps
  return $ 2 * p * q * r - p * q - q * r - r * p
      where ps = primesToLimit 5000 ::[Int]

Java:
import java.awt.*;
import java.io.*;
import java.math.*;
import java.util.*;
import java.awt.geom.*;
import java.lang.reflect.*;

public class Euler {
 
 
 public static void main(String[] args)
 {
  long sum = 0;
  java.util.List<long> primes = Primes.listOfPrimesUpTo(5000);
  for(int i = 0; i < primes.size(); i++)
   for(int j = i + 1; j < primes.size(); j++)
    for(int k = j + 1; k < primes.size(); k++)
     sum += smallestImpossible(primes.get(i), primes.get(j), primes.get(k));
  System.out.println(sum);
 }
 
 //smallest impossible number for linear combinations of pq, qr, and rp
 public static long smallestImpossible(long p, long q, long r)
 {
  return 2*p*q*r - (p*q + r*p + r*q);
 }
}

Basic:
Sub Prob_278()
Dim p(700) As Double
Dim mul(700, 700) As Double

pr = 2
i = 1

' loads primes p(i) under 5000
Do
 p(i) = pr
 pr = NextPrime(pr)
 i = i + 1
Loop While pr < 5000
n = i - 1 'number of primes

'generates two primes multipl.
For i = 2 To n
 For j = 1 To i - 1
  mul(j, i) = p(j) * p(i)
 Next j
Next i

s = 0
s2 = 0

For i = 1 To n - 2
 For j = i + 1 To n - 1
  For k = j + 1 To n
   s1 = mul(1, j) * mul(i, k) - mul(i, j) - mul(i, k) - mul(j, k)
   's1 = 2 * p(j) * p(k) * p(i) - p(i) * p(j) - p(i) * p(k) - p(j) * p(k)
   s = s + s1
   s2 = ModBig(s2 + ModBig(s1, 10000000000#), 10000000000#)
  Next k
 Next j
Next i

MsgBox (Int(s / 10000000000#) & s2)
End Sub

Herhangi Matematiksel Şeyler

Sayfalar

10 Ocak 2020

Euler Projesi 278. Soru