;; -*- coding: utf-8 -*-
;; ---
;; jupyter:
;;   jupytext:
;;     text_representation:
;;       extension: .scm
;;       format_name: light
;;       format_version: '1.5'
;;       jupytext_version: 1.14.4
;;   kernelspec:
;;     display_name: Calysto Scheme 3
;;     language: scheme
;;     name: calysto_scheme
;; ---

;; ### 練習問題1.27
;; Footnote 1.47で挙げたカーマイケル数が実際にフェルマーテストを騙すということを実験せよ。  
;; それはつまり、整数$n$を取り、すべての$a<n$について$a^n$が法$n$
;; に関して$a$と合同になるかテストする⼿続きを書き、  
;; 与えられたカーマイケル数に対してその⼿続きを試すということになる。

;; カーマイケル数  
;; 561, 1105, 1729, 2465, 2821, 6601
;;

(define (expmod base exp m)
  (cond ((= exp 0) 1)
        ((even? exp)(remainder (square (expmod base (/ exp 2) m)) m))
        (else (remainder (* base (expmod base (- exp 1) m)) m)))
  )
(define (square x)(* x x))

(define (loop p)
  (define (loop-iter n)
    (if (<= n p)
        (begin
         (display n)
         (display " ")
         (display p)
         (display " ")
         (display p)
         (display " ")
         (display (= (expmod n p p) (remainder n p)))
         (newline)
         (loop-iter (+ n 1))
         )
    )
   )
  (loop-iter 1)
  (newline)
  )

(loop 13)
(loop 17)
(loop 21)

(define (loop p)
  (define (loop-iter n)
    (if (<= n p)
        (begin
         (if (not (= (expmod n p p) (remainder n p)))
             (begin
              (display "not primary")
              (newline)
              #f
              )
             (loop-iter (+ n 1))
             )
         )
        #t
    )
   )
  (loop-iter 1)
  )

(display (loop 17))

(display (loop 21))

(loop 561)

(loop 1105)

(loop 1729)

(loop 2465)

(loop 2821)

(loop 6601)

StarcoderdataJupyterScriptsDedupFiltered