Herhangi Matematiksel Şeyler: Euler Projesi 243. Soru

Direnç

Payı paydasından küçük olan bir pozitif kesre basit kesir denir. Herhangi bir d paydası için d − 1 adet basit kesir olacaktır; örneğin d = 12 için 1/12, 2/12, 3/12, 4/12, 5/12, 6/12, 7/12, 8/12, 9/12, 10/12, 11/12.

Sadeleşmeyen basit bir kesre dirençli kesir adını verelim. Dahası, bir d paydasının R(d) direncini, dirençli kesirlerin basit kesirlere oranı olarak tanımlayalım; örneğin R(12) = 4/11. Aslında d = 12, R(d) < 4/10 direncine sahip en küçük paydadır.

R(d) < 15499/94744 direncine sahip olan en küçük d paydasını bulunuz.

Cevap: 892371480

Mathematica:

f[x_] := Module[{r, n, t},
  r[n_] := EulerPhi@n/(n - 1);
  t[n_] := Times @@ Table[Prime@i, {i, n}];
  n = NestWhile[# + 1 &, 2, r@t@# >= x &] - 1;
  t@n*NestWhile[# + 1 &, 2, r@(t@n*#) >= x &]]
f[15499/94744] // AbsoluteTiming

Python:

divv x y = fromInteger x / fromInteger y

loop :: [Integer] -> Integer -> Integer -> Int -> Double -> Int
loop (x:xs) n phi l c
    | divv count (prod - 1) < c = l
    | otherwise = loop xs prod count (l + 1) c
    where prod = n * x
          count = phi * (x - 1)

p243 :: Double -> Integer
p243 m = s * denom
    where c = loop primes 1 1 0 m
          l = take c primes
          numer = product (map (\x -> x - 1) l)
          denom = product l

          looper k | r < m = k
                   | otherwise = looper (k + 1)
                   where r = divv (k * numer) (k * denom - 1)
          s = looper 2

getAnswer = p243 (15499 /94744)

C#:

  static void Euler243()
    {
      uint lPrimeCnt = 10000;
      MathExtPNF.initMathExtPrimes(lPrimeCnt);

      double lMax = 15499.0 / 94744.0;
      double dVal=1;
      ulong lStart = 1;

      for (ulong i=2;i

Maple:

with(numtheory);
r:=x->phi(x)/(x-1);
p:=x->r(x)-15499/94744;
p(2*3*5*7*11*13*17*19*23);
                                11209
                            --------------
                            21136710780536
p(2*3*5*7*11*13*17*19*23*27);
                               -100331
                           ---------------
                           570691193537816
p(2*3*5*7*11*13*17*19*23*2);
                                 6919
                            --------------
                            42273421655816
p(2*3*5*7*11*13*17*19*23*4);
                                -1661
                            --------------
                            84546843406376
2*3*5*7*11*13*17*19*23*4;
                              892371480

C++:


#include 
#include  $#include #include #define s64 __int64
using namespace std;

void Factorise(s64 n, vector & v)
{
 s64 root = (s64)sqrt((double)n) + 1;
 for (s64 i = 2; i <= root && n != 1;) {
  if (n % i == 0) {
   n /= i;
   v.push_back(i);
   continue;
  }
  i ++;
 }
 if (n != 1) v.push_back(n);
}

s64 Rad(s64 n) {
 vector v;
 Factorise(n, v);
 v.erase(unique(v.begin(), v.end()), v.end());
 s64 ret = 1;
 for (vector ::size_type t = 0; t < v.size(); t ++)
  ret *= v[t];
 return ret;
}

s64 Phi(s64 n) {
 vector v;
 Factorise(n, v);
 v.erase(unique(v.begin(), v.end()), v.end());
 s64 ret = n;
 for (vector ::size_type t = 0; t < v.size(); t ++) 
  ret = ret * (v[t] - 1) / v[t];
 return ret;
}

int main(int argc, char* argv[]) {
 s64 dp = 1, d = 1;
 while (true) {
  // Not efficient because Factorise() is called twice.
  d = dp + Rad(dp);
  dp = d;
  double r = (double)Phi(d) / (d - 1);
  if (r < 15499.0 / 94744.0) {
   printf("d:%I64d, r:%.15lf\n", d, r);
   break;
  }
 }
}$

Java:

import java.math.BigInteger;

public class Prob243 extends Prob
{
 public static void main(String[] args)
 {
  initPrimes(10000000); // defined in Prob, used by totient()
  double target = 15499/94744.0;
  long[] primorials = new long[]{
   1, 2, 2*3, 2*3*5, 2*3*5*7, 2*3*5*7*11,
   2*3*5*7*11*13, 2*3*5*7*11*13*17,
   2*3*5*7*11*13*17*19,
   2*3*5*7*11*13*17*19*23,
   2L*3*5*7*11*13*17*19*23*29};
  int i = 0;
  long val = 1;
  long curr = primorials[i];
  long next = primorials[i+1];
  for (int q = 0; q < 100; q++)
  {
   // totient() defined in Prob
   double f = totient(val) / (double)(val - 1);
   if (f < target)
   {
    System.out.println(val);
    return;
   }
   val += curr;
   if (val >= next)
   {
    i++;
    curr = next;
    next = primorials[i+1];
   }
  }
 }
}

Herhangi Matematiksel Şeyler

Sayfalar

3 Temmuz 2018

Euler Projesi 243. Soru