; floyd's triangle

(define (floyd1 n)
  (let ((num 1))
    (do ((i 0 (+ i 1))) ((<= n i))
      (do ((j 0 (+ j 1))) ((< i j))
        (display num)
        (display (if (< j i) #\space #\newline))
        (set! num (+ num 1))))))

(floyd1 10)

(define (isqrt n)
  (if (not (and (positive? n) (integer? n)))
      (error 'isqrt "must be positive integer")
      (let loop ((x n))
        (let ((y (quotient (+ x (quotient n x)) 2)))
          (if (< y x) (loop y) x)))))

(define (square? n)
  (define bitwise-and logand)
  (let ((m (modulo n 128)))
    (if (positive? (bitwise-and (* m #x8bc40d7d) (* m #xa1e2f5d1) #x14020a)) #f
      (let ((large-mod (modulo n 3989930175))) ; (* 63 25 11 17 19 23 31)
        (and (let ((m (modulo large-mod 63)))
               (zero? (bitwise-and (* m #x3d491df7) (* m #xc824a9f9) #x10f14008)))
             (let ((m (modulo large-mod 25)))
               (zero? (bitwise-and (* m #x1929fc1b) (* m #x4c9ea3b2) #x51001005)))
             (let ((m (* #xd10d829a (modulo large-mod 31))))
               (zero? (bitwise-and m (+ m #x672a5354) #x21025115)))
             (let ((m (modulo large-mod 23)))
               (zero? (bitwise-and (* m #x7bd28629) (* m #xe7180889) #xf8300)))
             (let ((m (modulo large-mod 19)))
               (zero? (bitwise-and (* m #x1b8bead3) (* m #x4d75a124) #x4280082b)))
             (let ((m (modulo large-mod 17)))
               (zero? (bitwise-and (* m #x6736f323) (* m #x9b1d499) #xc0000300)))
             (let ((m (modulo large-mod 11)))
               (zero? (bitwise-and (* m #xabf1a3a7) (* m #x2612bf93) #x45854000)))
             (let ((root (isqrt n))) (if (= (* root root) n) root #f)))))))

(define (floyd2 n)
  (let ((row 0))
    (do ((num 1 (+ num 1))) ((= row n))
      (display num)
      (if (square? (+ (* 8 num) 1))
          (begin (display #\newline)
                 (set! row (+ row 1)))
          (display #\space)))))

(floyd2 10)