Herhangi Matematiksel Şeyler: Euler Projesi 284. Soru

Kararlı Kareler

Ondalık sistemdeki 3 haneli 376 sayısı, karesi aynı rakamlarla biten özel nitelikteki sayılara bir örnektir: 376² = 141376. Bu özelliğe sahip bir sayıya bir kararlı kare diyelim.

Diğer sayı sistemlerinde de sabit kareler gözlemlenebilir. 14 tabanlı sayı sisteminde, 3 basamaklı c37 sayısı da bir kararlı karedir: c37² = aa0c37 ve aynı sayı sisteminde basamaklarının toplamı c + 3 + 7 = 18'dir. a, b, c ve d harfleri, onaltılık sayı sistemine benzer şekilde sırasıyla 10, 11, 12 ve 13 basamak değerleri için kullanılır.

1 ≤ n ≤ 9 için, 14 tabanlı sayı sistemindeki tüm n basamaklı kararlı karelerin rakamlarının toplamı 2d8'dir (582 ondalık). Başında 0 bulunan kararlı karelere izin verilmez.

1 ≤ n ≤ 10000 (ondalık) için 14 tabanlı sayı sistemindeki tüm n basamaklı kararlı karelerin rakamlarının toplamını bulun ve cevabınızı 14 tabanlı sistemde gerekli yerlerde küçük harflerle verin. Cevap: 5a411d7b

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

#define N 10000

long long int d[N+1][N+1];

long long int answer = 0;
void recur(int nth, int sum);

long long int a;
int an;
int ad[N+1];

int main(int argc, char **argv) {
  int i, j;
  int s;
  for (i=1; i<14; i++) { // 0 is excluded
    s = i*i;
    if (s%14==i) {
      d[0][0] = i;
      d[0][1] = s/14;
      answer += i;
      recur(1,i);
    }
  }

printf ("ans %lld\n", answer);
  
  a = answer;
  an = 0;
  while (a) {
    ad[an++] = a%14;
    a /= 14;
  }
  for (i=an-1; i>=0; i--)
    printf ("%x", ad[i]);
  printf ("\n");
}
 
void recur(int nth, int sum) {
  int i, j;

for (i=0; i<=N; i++)
    d[nth][i] = d[nth-1][i];

for (i=0; i<14; i++) {
    if (nth*2 <=N)
      d[nth][nth*2] += i*i;
    if ((d[nth][nth]-i)%14==0) {
      d[nth][nth+1] += d[nth][nth]/14;
      d[nth][nth] = d[nth][nth]%14;
      if (i!=0) {
      answer += i;
      for (j=0; j<nth; j++)
	answer += d[nth][j];
      }
      if (nth < N-1)
	recur (nth+1, sum+i);
    }
    for (j=0; j<nth; j++) {
      if (nth+j > N)
	break;
      d[nth][nth+j] += d[nth-1][j]*2;
    }
    if (nth*2 <=N)
      d[nth][nth*2] -= i*i;
    
  }
}
                  
Python:
def find_all(n, x, a, add, tot):
    res = 0
    for k in xrange(1, n + 1):
        if a[-1] != 0: res += tot
        cursum = sum(a[i] * a[k-i] for i in xrange(1, k)) + add
        for ak in xrange(x):
            val = 2 * a[0] * ak + cursum
            if val % x == ak:
                a.append(ak)
                add = val // x
                tot += ak
    return res

def find(n, x):
    res = 0
    for a0 in xrange(x):
        val = a0 * a0
        if val % x == a0:
           res += find_all(n, x, [a0], val // x, a0)
    print res

find(10000, 14)
                  
Java:
x = {7};
y = {8};
z = 1 + 7 + 8;
Timing[
  While[
    Length[x] < 10000 && Length[y] < 10000,
    For[
      i = 13,
      i > 0 && RealDigits[FromDigits[Prepend[x, i], 14]^2, 14][[1, (1 + Length[RealDigits[FromDigits[Prepend[x, i], 14]^2, 14][[1]]] - Length[Prepend[x, i]]) ;; -1]] != Prepend[x, i],
      i--
    ];
    x = Prepend[x, i];
    If[i != 0, z += Total[x]];
    For[
      i = 13,
      i > 0 && RealDigits[FromDigits[Prepend[y, i], 14]^2, 14][[1, (1 + Length[RealDigits[FromDigits[Prepend[y, i], 14]^2, 14][[1]]] - Length[Prepend[y, i]]) ;; -1]] != Prepend[y, i],
      i--
    ];
    y = Prepend[y, i];
    If[i != 0, z += Total[y]]
  ];
  {Length[x], Length[y], z, RealDigits[z, 14][[1]]}
]
  
ml:
open Format

let limit = int_of_string Sys.argv.(1)
let base = 14

(* numbers in base 14 as lists, with least significant digits first *)

let rec add_digit d = function
  | [] -> [d]
  | dx :: x when d+dx < base -> d+dx :: x
  | dx :: x -> d+dx-base :: add_digit 1 x

let rec add x y = match x, y with
  | [], s | s, [] -> s
  | dx :: rx, dy :: ry when dx+dy < base -> dx+dy :: add rx ry
  | dx :: rx, dy :: ry -> dx+dy-base :: add_digit 1 (add rx ry)

let rec shift n x = if n = 0 then x else 0 :: shift (n-1) x

let rec mul_digit d = function
  | [] -> 
      []
  | dx :: x -> 
      let z = d * dx in
      let c = z / base in
      let r = mul_digit d x in
      z mod base :: if c = 0 then r else add_digit c r

let rec mul x = function
  | [] -> []
  | dy :: ry -> add (mul_digit dy x) (0 :: mul x ry)

let sum = ref [1] (* solution 1 *)

let rec sum_digits = function
  | [] -> []
  | d :: r -> add_digit d (sum_digits r)

let leading_zero = function
  | 0 :: _ -> true
  | _ -> false

let rec search n p rev_s =
  (* s has n digits and s^2 = ps *)
  if not (leading_zero rev_s) then sum := add !sum (sum_digits rev_s);
  let two_s = mul_digit 2 (List.rev rev_s) in
  if n < limit then begin
    (* OPTIM: there is exactly one possible digit x => tail call *)
    let rec search_digit x =
      assert (x < base);
      let x2 = mul [x] [x] in
      let hi = add (shift n x2) (add (mul_digit x two_s) p) in
      match hi with
	| d :: p when d = x -> search (n+1) p (x :: rev_s)
	| _ -> search_digit (x+1)
    in
    search_digit 0
  end

let print_digit fmt = function
  | d when d < 10 -> fprintf fmt "%d" d
  | d when d < base -> fprintf fmt "%c" (Char.chr (Char.code 'a' + d - 10))
  | _ -> assert false

let rec print fmt = function
  | [] -> ()
  | x :: r -> fprintf fmt "%a%a" print r print_digit x

let () = 
  search 1 [3] [7]; (* 7^2 = 37 *)
  search 1 [4] [8]; (* 8^2 = 48 *)
  printf "solution = %a@." print !sum

Herhangi Matematiksel Şeyler

Sayfalar

17 Kasım 2020

Euler Projesi 284. Soru