10 Nisan 2017

Euler Projesi 218. Soru

Perfect right-angled triangles

Kenar uzunlukları a=7, b=24 ve c=25 olan dik üçgeni düşünün. Alanı 84 olup 6 ve 28 mükemmel sayılarıyla bölünebilir.

Dahası bir ilkel dik üçgendir, yani ebob(a,b)=1 ve ebob(b,c)=1. Ayrıca c bir tam karedir. Bir dik üçgene ilkel olması ve hipotenüsünün tam kare olması durumunda mükemmel denir.

Bir dik üçgene mükemmel olması ve alanının 6 ile 28 mükemmel sayıları ile bölünebilmesi durumunda süper-mükemmel denir.

c≤1016 olmak üzere kaç tane süper olmayan mükemmel dik üçgen vardır?

Cevap: 0

Maple:
roxx:=proc(p,q)
> [abs((p^2-q^2)^2-(2*p*q)^2),2*(p^2-q^2)*2*p*q,(p^2-q^2)^2+4*(p*q)^2]
> end:

roxxx:=proc(n)
> local som,i,j,flag,t,a,b,c;
> som:=0;
> for i from 1 to floor(sqrt(sqrt(n))) do
> for j from 1 to i-1 do
>   flag:=false;
>   t:=roxx(i,j);
>   if t[3]>n then break else
>     c:=t[3];
>     a:=min(t[1],t[2]);
>     b:=max(t[1],t[2]);
>     if gcd(a,b)=1 and gcd(b,c)=1 then flag:=true fi;
>     if flag=true then 
>      if a*b/2 mod 6=0 and a*b/2 mod 28 =0 then flag:=false fi;
>      fi;
>     if flag=true then som:=som+1; print(a,b,c) fi;
>   fi;
> od;
> od;
> som
> end:

Pascal:
program kikou;
uses minimaple;

var t:array[1..3] of int64;

procedure roxx(p,q:longint);
var a,b,c:int64;
begin
  a:=(p*p-q*q);
  b:=2*p*q;
  c:=(p*p+q*q);
  c:=c*c;
  t[1]:=abs(a*a-b*b);
  t[2]:=2*a*b;
  t[3]:=a*a+b*b;
end;

function min(a,b:int64):int64;
begin
  if a<b then min:=a else min:=b;
end;

function max(a,b:int64):int64;
begin
  if a>b then max:=a else max:=b;
end;

function roxxx(n:int64):longint;
var som,a,b,c:int64;
    flag:boolean;
    i,j:longint;
begin
  som:=0;
  for i:=1 to trunc(sqrt(sqrt(n+0.0))) do
  for j:=1 to i-1 do
  begin
    flag:=false;
    roxx(i,j);
    if t[3]>n then break else
    begin
      c:=t[3];
      a:=min(t[1],t[2]);
      b:=max(t[1],t[2]);
      if (pgcd(a,b)=1) and (pgcd(b,c)=1) then flag:=true;
      if flag=true then
      if (((a*b) div 2) mod 6=0) and (((a*b) div 2) mod 28=0) then flag:=false;
      if flag=true then som:=som+1;
    end;
  end;
  roxxx:=som;
end;

begin
  writeln(roxxx(10000000000000000));
end.

C+:
#include <cstdio>
#include <cmath>

typedef long long ULL;

template<typename T> T Abs(T x) {
        return (x >= 0) ? x : -x;
}

int main() {
        const ULL top = 10000;
        const ULL top2 = 100000000;
        const ULL top3 = top2*top2;
        fprintf(stderr, "%lld\n", top3);
        for (ULL n = 1; n <= top; ++n) {
                if (0 == n % 10)
                        fprintf(stderr, "%lld\n", n);
                ULL topM = (ULL)sqrt(top - n*n);
                for (ULL m = n + 1; m <= topM; ++m) {
                        ULL a = m*m - n*n;
                        ULL b = 2*m*n;
                        ULL c = m*m + n*n;

                        if (a < top2 && b < top2) {
                                ULL aa = Abs(a*a - b*b);
                                ULL bb = 2*a*b;
                                ULL cc = a*a + b*b;

                                if ( (aa*bb) % 168 && (cc <= top3) ) {
                                        printf("%lld %lld %lld\n", aa, bb, cc);
                                }
                        }
                }
        }

        return 0;
}

Mathematica:

f[u_, v_] := {v^2 - u^2, 2 u v, u^2 + v^2}
For[cnt = 0; i = 1, i <= 10^4, i++,
 If[Divisible[i, 3] || Divisible[i, 7], Continue[]]; 
 z = Min[i, Sqrt[10^8 - i^2]]; 
 For[j = 1 + Boole[OddQ[i]], j <= z, j += 2,
  If[CoprimeQ[i, j] && 
    Divisible[-2 i j (i^2 - j^2) (i^4 - 6 i^2 j^2 + j^4), 84], cnt++]]]
cnt

Java:
import java.util.*;
import java.math.*;
import static java.lang.Math.*;
import static java.lang.System.*;

public class P218 {//kevinsogo
 static long L;
 static int M;
 static int N;
 public static void main (String args[]) {
  L = args.length == 0 ? (long)1e16 : Long.parseLong(args[0]);
  M = (int)floor(sqrt(L));
  N = (int)floor(sqrt(M));
  BoolArray a = new BoolArray((M >> 2) + 1);
  short as[] = new short[(M >> 2) + 1];
  short bs[] = new short[(M >> 2) + 1];
  for (int j = 0; ((j << 2) + 3) <= N; j++) {
   int p = 0;
   for (int k = j; (p = ((j << 2) + 3)*((k << 2) + 3)) <= M; k++) {
    a.set(p >> 2, true);
   }
  }
  for (int aa = 1; (aa * aa) << 1 <= M; aa++) {
   for (int bb = aa; aa * aa + bb * bb <= M; bb++) {
    if (gcd(aa, bb) != 1) continue;
    int n = aa * aa + bb * bb;
    if ((n & 3) == 1) {
     int k = n >> 2;
     as[k] = (short)aa;
     bs[k] = (short)bb;
    }
   }
  }
  int count = 0;
  int av[] = new int[100];
  int bv[] = new int[100];
  int cv = 0;
  for (int i = 1; (i << 2) + 1 <= M; i++) {
   if (!a.get(i)) {
    cv = 0;
    int n = (i << 2) + 1;
    for (int j = 1, k = 5; k * k <= n; j++, k += 4) {
     if (n % k == 0) {
      int ai = as[j];
      int bi = bs[j];
      while ((n /= k) % k == 0) {
       int aj = abs(ai * as[j] - bi * bs[j]);
       int bj = bi * as[j] + ai * bs[j];
       ai = aj;
       bi = bj;
      }
      if (cv == 0) {
       av[cv] = ai;
       bv[cv] = bi;
       cv++;
      } else for (int l = cv - 1; l >= 0; l--) {
       av[cv] = abs(ai * av[l] - bi * bv[l]);
       bv[cv] = bi * av[l] + ai * bv[l];
       int al = abs(ai * bv[l] - bi * av[l]);
       int bl = bi * bv[l] + ai * av[l];
       av[l] = al;
       bv[l] = bl;
       cv++;
      }
     }
    }
    if (n > 1) {
     int j = n >> 2;
     int ai = as[j];
     int bi = bs[j];
     if (cv == 0) {
      av[cv] = ai;
      bv[cv] = bi;
      cv++;
     } else for (int l = cv - 1; l >= 0; l--) {
      av[cv] = abs(ai * av[l] - bi * bv[l]);
      bv[cv] = bi * av[l] + ai * bv[l];
      int al = abs(ai * bv[l] - bi * av[l]);
      int bl = bi * bv[l] + ai * av[l];
      av[l] = al;
      bv[l] = bl;
      cv++;
     }
    }
    for (int j = 0; j < cv; j++) {
     long aa = av[j], bb = bv[j];
     long aA = abs(aa*aa - bb*bb), bB = ((aa*bb) << 1);
     long AA = abs(aA*aA - bB*bB), BB = ((aA*bB) << 1);
     long AAA = (AA & 1) == 0 ? AA >> 1 : AA, BBB = (AA & 1) == 0 ? BB : BB >> 1;
     long marea = ((AAA % 84) * (BBB % 84)) % 84;
     if (marea != 0) {
      if (gcd(AA, BB) != 1) continue;
      n = (i << 2) + 1;
      out.println(n + "^1. " + aa + "^2 + " + bb + "^2");
      out.println(n + "^2. " + aA + "^2 + " + bB + "^2");
      out.println(n + "^4. " + AA + "^2 + " + BB + "^2");
      out.println("area = " + marea + " mod 84");
      count++;
     }
    }
   }
  }
  out.println(count);
 }
 static long gcd(long a, long b) {
  return b == 0 ? a : gcd(b, a % b);
 }
 static class BoolArray {
  long values[];
  int n;
  BoolArray(int n) {
   this.n = n;
   values = new long[(n + ((1 << 6) - 1)) >> 6];
  }
  void set(int i, boolean b) {
   if (get(i) != b) values[i >> 6] ^= 1l << (i % 64);
  }
  boolean get(int i) {
   return (values[i >> 6] & (1l << (i % 64))) != 0;
  }
 }

}