;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; ;;
;; http://www.research.att.com/~njas/sequences/GF2Xfuns.scm.txt ;;
;; ;;
;; Coded by Antti Karttunen (Antti.Karttunen(-AT-)iki.fi), ;;
;; at the turn of 2003-2004. ;;
;; ;;
;; This file contains the Scheme-functions that compute the sequences ;;
;; A091202-A091233 & A091238-A091257 ;;
;; found in ;;
;; Neil Sloane's On-Line Encyclopedia of Integer Sequences (OEIS) ;;
;; available at ;;
;; http://www.research.att.com/~njas/sequences/ ;;
;; ;;
;; Copy of THIS source file is also available at: ;;
;; http://www.iki.fi/~karttu/matikka/Schemuli/GF2Xfuns.scm ;;
;; ;;
;; This Scheme-code is in Public Domain and runs (at least) ;;
;; in MIT Scheme Release 7.7.x, for which one can find documentation ;;
;; and the pre-compiled binaries (for various OS's running in ;;
;; Intel x86 architecture) under the URL: ;;
;; http://www.swiss.ai.mit.edu/projects/scheme/ ;;
;; ;;
;; Aubrey Jaffer's SLIB Scheme library is available at: ;;
;; http://www.swiss.ai.mit.edu/~jaffer/SLIB.html ;;
;; I have used the version 3a1 from November 2003. ;;
;; ;;
;; If you have improvements, suggestions, additions, please send them ;;
;; to me with e-mail (with subject TOPIC: GF2Xfuns.scm) and I can edit ;;
;; them to this program. Alternatively, you can send the improved ;;
;; program directly to Neil Sloane. ;;
;; ;;
;; Last edited 3. Jan 2004 by Antti Karttunen. ;;
;; ;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;
;; To be able to load this module, you must have
;; started your MIT Scheme interpreter as:
;;
;; export MITSCHEME_LARGE_HEAP=5000
;; scheme -large
;;
(declare (usual-integrations))
(load "/usr/local/lib/slib/mitscheme.init") ;; A. Jaffer's SLIB Scheme library.
(require 'factor) ;;
;; See the C++ program GF2Xfacs.c at the this file, to understand
;; how these precomputed vectors have been computed:
(define GF2X_FACVEC (fasload "GF2Xffff.vec"))
(define (GF2Xfactor n) (vector-ref GF2X_FACVEC n))
(define Xn_1_FACVEC (fasload "Xn_1_511.vec")) ;; Note. the data is invalid after n=31.
(define (Xn_1factor n) (vector-ref Xn_1_FACVEC n))
;; Example: (map GF2Xfactor (iota 17))
;; results: (() (2) (3) (2 2) (3 3) (2 3) (7) (2 2 2) (3 7) (2 3 3) (11)
;; (2 2 3) (13) (2 7) (3 3 3) (2 2 2 2) (3 3 3 3))
;;
;; Example: (map Xn_1factor (iota 17))
;; results: ((3) (3 3) (3 7) (3 3 3 3) (3 31) (3 3 7 7) (3 11 13)
;; (3 3 3 3 3 3 3 3) (3 7 73) (3 3 31 31) (3 2047)
;; (3 3 3 3 7 7 7 7) (3 8191) (3 3 11 11 13 13) (3 7 19 25 31)
;; (3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3) (3 313 471))
;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; ;;
;; Copied from http://www.iki.fi/~kartturi/matikka/Schemuli/definech.scm ;;
;; ;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; define unary cached functions. Syntax is like
;; (define (func arg) ...) of Scheme.
;; Note that this and other cached functions depend on MIT Scheme
;; peculiarities, like that vectors are initialized to contain #f's
;; and also that #f is actually same thing as (). To be corrected.
;; Added this 10. July 2002 to avoid allocation catastrophes
;; caused by the careless use of the cached integer functions:
(define *MAX-CACHE-SIZE-FOR-DEFINEC* 290512) ;; Was 131072
(define-syntax definec
(syntax-rules ()
((definec (name arg) e0 ...)
(define name
(letrec
((_cache_ (vector #f #f #f #f #f #f #f #f #f #f #f #f #f #f #f #f))
(name
(lambda (arg)
(cond ((null? arg) _cache_)
((>= arg *MAX-CACHE-SIZE-FOR-DEFINEC*)
e0 ...
)
(else
(if (>= arg (vector-length _cache_))
(set! _cache_
(vector-grow
_cache_
(min *MAX-CACHE-SIZE-FOR-DEFINEC*
(max (1+ arg)
(* 2 (vector-length _cache_))
)
)
)
)
)
(or (vector-ref _cache_ arg)
((lambda (res)
(vector-set! _cache_ arg res)
res
)
(begin e0 ...)
)
)
)
) ; cond
)
)
) ; letrec-definitions
name
) ; letrec
) ;; (define name ...)
)
) ;; syntax-rules
)
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; ;;
;; Copied from http://www.iki.fi/~kartturi/matikka/Schemuli/intfuns1.scm ;;
;; ;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(definec (binomial_n_2 n) (/ (* (-1+ n) n) 2))
(definec (A025581 n) ;; The X component (column) of square {0..inf} arrays
(- (binomial_n_2 (1+ (floor->exact (flo:+ 0.5 (flo:sqrt (exact->inexact (* 2 (1+ n)))))))) (1+ n))
)
;; (map A002262 (cons 0 (iota 20))) --> (0 0 1 0 1 2 0 1 2 3 0 1 2 3 4 0 1 2 3 4 5)
(definec (A002262 n) ;; The Y component (row) of square {0..inf} arrays
(- n (binomial_n_2 (floor->exact (flo:+ 0.5 (flo:sqrt (exact->inexact (* 2 (1+ n))))))))
)
(define (A002024 n) ;; repeat n n times, starting from n = 1.
(floor->exact (+ (/ 1 2) (sqrt (* 2 n))))
)
(define (A003056 n) ;; repeat n n+1 times, starting from n = 0.
(floor->exact (- (sqrt (* 2 (1+ n))) (/ 1 2)))
)
(define (A001477 n) n)
(define (A000079 n) (expt 2 n))
(define (A000225 n) (-1+ (A000079 n)))
(define (A000051 n) (1+ (A000079 n)))
;; Offset=0: 2,3,5,9,17,33,65,129,257,513,
(define (A000523 n) (cond ((zero? n) -1) (else (floor->exact (/ (log n) (log 2))))))
(define (binwidth n) ;; = A029837(n+1)
(let loop ((n n) (i 0))
(if (zero? n)
i
(loop (floor->exact (/ n 2)) (1+ i))
)
)
)
(define (obtain-integer-bitwise-function bit-string-FUN)
(lambda (x y)
(let ((size (max (binwidth x) (binwidth y))))
(bit-string->unsigned-integer
(bit-string-FUN (unsigned-integer->bit-string size x)
(unsigned-integer->bit-string size y)
)
)
)
)
)
(define A003986bi (obtain-integer-bitwise-function bit-string-or))
(define A003987bi (obtain-integer-bitwise-function bit-string-xor))
(define A004198bi (obtain-integer-bitwise-function bit-string-and))
(define (A007088 n) ;; 0,1,10,11,100,101,110,111,1000,... (Show binary form in decimal)
(let loop ((z 0) (i 0) (n n))
(if (zero? n)
z
(loop (+ z (* (expt 10 i) (modulo n 2)))
(1+ i)
(floor->exact (/ n 2))
)
)
)
)
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; ;;
;; Copied from http://www.iki.fi/~kartturi/matikka/Schemuli/lstfuns1.scm ;;
;; (always useful!) ;;
;; ;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(define (compose-funlist funlist)
(cond ((null? funlist) (lambda (x) x))
(else (lambda (x) ((car funlist) ((compose-funlist (cdr funlist)) x))))
)
)
(define (compose-funs . funlist)
(cond ((null? funlist) (lambda (x) x))
(else (lambda (x) ((car funlist) ((apply compose-funs (cdr funlist)) x))))
)
)
(define reversed_iota
(lambda (n)
(if (zero? n) (list)
(cons n (reversed_iota (- n 1)))
)
)
)
(define iota (lambda (n) (reverse! (reversed_iota n))))
(define (iota0 upto_n)
(let loop ((n upto_n) (result (list)))
(cond ((zero? n) (cons 0 result))
(else (loop (- n 1) (cons n result)))
)
)
)
;; For testing whether we have an identity permutation or not.
(define (first-dislocated lista)
(let loop ((lista lista) (i 0))
(cond ((null? lista) lista)
((not (equal? (car lista) i)) lista)
(else (loop (cdr lista) (1+ i)))
)
)
)
(define (pos-of-first-matching lista pred?)
(let loop ((lista lista) (i 0))
(cond ((null? lista) #f)
((pred? (car lista)) i)
(else (loop (cdr lista) (1+ i)))
)
)
)
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; ;;
;; Useful when counting the number of distinct prime divisors: ;;
;; ;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(define (distinct-elems lista)
(if (not (pair? lista))
0
(let loop ((n 0)
(lista lista)
(prev (not (car lista)))
)
(cond ((not (pair? lista)) n)
((equal? (car lista) prev) (loop n (cdr lista) prev))
(else (loop (1+ n) (cdr lista) (car lista)))
)
)
)
)
(define (multiplicities lista) ;; Of numeric elements.
(let loop ((mults (list))
(lista lista)
(prev #f)
)
(cond ((not (pair? lista)) mults)
((equal? (car lista) prev)
(set-car! mults (+ 1 (car mults)))
(loop mults (cdr lista) prev)
)
(else
(loop (cons 1 mults) (cdr lista) (car lista))
)
)
)
)
;; For doing GCD:
(define (m-intersect a b) ;; of sorted multisets of numeric elements.
(let loop ((a a)
(b b)
(c (list))
)
(cond ((or (not (pair? a)) (not (pair? b))) (reverse! c))
((equal? (car a) (car b))
(loop (cdr a) (cdr b) (cons (car a) c))
)
((< (car a) (car b))
(loop (cdr a) b c)
)
(else ;; I.e. (> (car a) (car b))
(loop a (cdr b) c)
)
)
)
)
;; For doing LCM:
(define (m-union a b) ;; of sorted multisets of numeric elements.
(let loop ((a a)
(b b)
(c (list))
)
(cond ((and (not (pair? a)) (not (pair? b))) (reverse! c))
((not (pair? a)) (loop a (cdr b) (cons (car b) c)))
((not (pair? b)) (loop (cdr a) b (cons (car a) c)))
((equal? (car a) (car b))
(loop (cdr a) (cdr b) (cons (car a) c))
)
((< (car a) (car b))
(loop (cdr a) b (cons (car a) c))
)
(else ;; I.e. (> (car a) (car b))
(loop a (cdr b) (cons (car b) c))
)
)
)
)
;; Examples:
;; (m-intersect (list 2 2 3 3 3 7 7 11 23 29 29 37) (list 2 3 3 3 3 3 3 5 7 29 31 37 37))
;; --> (2 3 3 3 7 29 37)
;; (m-union (list 2 2 3 3 3 7 7 11 23 29 29 37) (list 2 3 3 3 3 3 3 5 7 29 31 37 37))
;; --> (2 2 3 3 3 3 3 3 5 7 7 11 23 29 29 31 37 37)
;; (m-intersect (list 3 7 9) (list 2 4 6 8)) --> ()
;; (m-union (list 3 7 9) (list 2 4 6 8)) --> (2 3 4 6 7 8 9)
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; ;;
;; First, a few ordinary number theoretic functions. ;;
;; ;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; It's mandatory that the factors are sorted!
;; And we can cache them as well... And make other functions to
;; return correct values for n=1.
(definec (ifactor n) (cond ((< n 2) (list)) (else (sort (factor n) <))))
;; Prepared with:
;; (define vecA000040 (list->vector (primes> 0 6542)))
;; (vector-length vecA000040) --> 6542
;; (vector-ref vecA000040 0) --> 2
;; (vector-ref vecA000040 2) --> 5
;; (vector-ref vecA000040 6541) --> 65521
;; (map prime? (map (lambda (n) (+ 65520 n)) (iota 37)))
;; (#t () () () () () () () () () () () () () () () #t () #t () () () #t () () () () () () () #t () () () () () #t)
;; (fasdump vecA000040 "sA000040.vec")
(define vecA000040 (fasload "sA000040.vec"))
(define (A008578 n) ;; A008578 (non-composite numbers) ;; Was ithprime
(cond ((< n 3) (1+ n)) ;; 0 -> 1, 1 -> 2, 2 -> 3,
(else (vector-ref vecA000040 (- n 1)))
)
)
;; (define (A000040 n) (vector-ref vecA000040 (- n 1)))
(define A000040 A008578) ;; In practice it is good to covetly return also (A000040 0) as 1.
(define vecA001037 (vector 1 2 1 2 3 6 9 18 30 56 99 186 335 630 1161 2182 4080 7710 14532 27594))
(define (A001037 n) (vector-ref vecA001037 n))
(define vecA036378 (vector 0 1 1 2 2 5 7 13 23 43 75 137 255 464 872 1612 3030 5709 10749 20390))
(define (A036378 n) (vector-ref vecA036378 n))
(define (A010051 n) (if (prime? n) 1 0))
(define (A066247 n) (if (and (> n 3) (not (prime? n))) 1 0))
;; A000720: pi(n), the number of primes <= n.
;; i.e. partial sums of the corresponding characteristic function.
(definec (A000720 n)
(cond ((< n 2) 0)
(else (+ (A010051 n) (A000720 (- n 1))))
)
)
(definec (A007097 n) (if (zero? n) 1 (A000040 (A007097 (- n 1)))))
;; A049084: 0 unless n is a prime p(k) when a(n) = k.
;; 0,1,2,0,3,0,4,0,0,0,5,0,6,0,0,0,7,0,8,0,0,0,9,0,0,0,0,0,10,
(definec (A049084 n)
(cond ((not (prime? n)) 0)
(else
(let loop ((i 1))
(cond ((= (A008578 i) n) i)
((> i n)
(error "Error detected in A049084, index i " i
"larger than n: " n)
)
(else (loop (1+ i)))
)
)
)
)
)
;; tau(n): number of divisors of n.
(definec (A000005 n) (apply * (map 1+ (multiplicities (ifactor n)))))
(definec (A001221 n) (distinct-elems (ifactor n)))
(definec (A001222 n) (length (ifactor n)))
(define (A008683 n) ;; Moebius mu
(cond ((= 1 n) n)
((not (= (A001221 n) (A001222 n))) 0) ;; Well, contains a square!
(else (expt -1 (A001222 n)))
)
)
;; Easy definition for Thue-Morse (parity) sequence:
(definec (A010060 n)
(cond ((zero? n) 0)
((even? n) (A010060 (/ n 2)))
(else (- 1 (A010060 (/ (- n 1) 2))))
)
)
;; %S A061775 1,2,3,3,4,4,4,4,5,5,5,5,5,5,6,5,5,6,5,6,6,6,6,6,7,6,7,6,6,7,6,6,7,6,7,7,
;; %N A061775 Number of nodes in rooted tree with Goebel number n.
(definec (A061775 n)
(cond ((<= n 1) n)
((= 1 (A010051 n)) (+ 1 (A061775 (A049084 n)))) ;; Planted tree.
(else (fold-left + 1 (map -1+ (map A061775 (ifactor n))))) ;; Combination of trees.
)
)
(define vecA000081 (vector 0 1 1 2 4 9 20 48 115 286 719 1842 4766 12486 32973 87811 235381))
(define (A000081 n) (vector-ref vecA000081 n))
;; This date taken directly from OEIS:
(define vecA005517 (vector 1 2 3 5 9 15 25 45 75 125 225 375 625 1125 1875 3125
5625 9375 15625 28125 46875 78125 140625 234375
390625 703125 1171875 1953125 3515625 5859375
9765625 17578125 29296875 48828125))
(define vecA005518 (vector 1 2 4 8 19 67 331 2221 19577 219613 3042161 50728129
997525853 22742734291 592821132889 17461204521323))
(define (A005517 n) (vector-ref vecA005517 (- n 1)))
(define (A005518 n) (vector-ref vecA005518 (- n 1)))
;; We can also compute them, but it is extremely slow when done dumbly:
(definec (A005517v2 n)
(cond
((<= n 1) n)
(else
(let loop ((i 0)) ;; Do it in dumb way!
(cond ((= (A061775 i) n) i)
(else (loop (+ 1 i)))
)
)
)
)
)
(definec (A005518v2 n)
(cond
((<= n 1) n)
(else
(let loop ((i 0) ;; Do it in dumb way!
(k-to-skip (- (A000081 n) 1))
)
(cond ((= (A061775 i) n)
(if (zero? k-to-skip)
i
(loop (+ 1 i) (- k-to-skip 1))
)
)
(else (loop (+ 1 i) k-to-skip))
)
)
)
)
)
;; Note that (A091238 n) = (A061775 (A091205 n))
;; and vice versa, (A061775 n) = (A091238 (A091204 n))
(definec (A091238 n)
(cond ((<= n 1) n)
((= 1 (A091225 n)) (+ 1 (A091238 (A091227 n)))) ;; Planted tree.
(else (fold-left + 1 (map -1+ (map A091238 (GF2Xfactor n))))) ;; Combination of trees.
)
)
(definec (A091239 n)
(cond
((<= n 1) n)
(else
(let loop ((i 0)) ;; Do it in dumb way!
(cond ((= (A091238 i) n) i)
(else (loop (+ 1 i)))
)
)
)
)
)
(definec (A091240 n)
(cond
((<= n 1) n)
(else
(let loop ((i 0) ;; Do it in dumb way!
(k-to-skip (- (A000081 n) 1))
)
(cond ((= (A091238 i) n)
(if (zero? k-to-skip)
i
(loop (+ 1 i) (- k-to-skip 1))
)
)
(else (loop (+ 1 i) k-to-skip))
)
)
)
)
)
;; Compare to A091233:
(define (A091241 n) (1+ (- (A091240 n) (A091239 n))))
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; ;;
;; GF2[X] related function follow. ;;
;; ;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; A091202: "Multiplicative" isomorphism from integers to GF2X-polynomials:
(definec (A091202 n)
(cond ((< n 2) n)
((= 1 (A010051 n)) (A014580 (A049084 n)))
(else (reduce A048720bi 1 (map A091202 (ifactor n))))
)
)
;; A091203: "Multiplicative" isomorphism from GF2X-polynomials to integers:
(definec (A091203 n)
(cond ((< n 2) n)
((= 1 (A091225 n)) (A000040 (A091227 n)))
(else (reduce A004247bi 1 (map A091203 (GF2Xfactor n))))
)
)
;; A091204: "Deeply multiplicative" isomorphism from integers to GF2X-polynomials:
(definec (A091204 n)
(cond ((< n 3) n)
((= 1 (A010051 n)) (A014580 (A091204 (A049084 n))))
(else (reduce A048720bi 1 (map A091204 (ifactor n))))
)
)
;; A091205: "Deeply multiplicative" isomorphism from GF2X-polynomials to integers:
(definec (A091205 n)
(cond ((< n 3) n)
((= 1 (A091225 n)) (A000040 (A091205 (A091227 n))))
(else (reduce A004247bi 1 (map A091205 (GF2Xfactor n))))
)
)
;; Data taken from OEIS: (Somewhat slowish to compute, I mean.)
(define vecA007053 (vector 0 1 2 4 6 11 18 31 54 97 172 309 564 1028 1900 3512
6542 12251 23000 43390 82025 155611 295947 564163 1077871
2063689 3957809 7603553 14630843 28192750 54400028
105097565 203280221 393615806 762939111 1480206279
2874398515 5586502348 10866266172 21151907950 41203088796
80316571436 156661034233 305761713237 597116381732
1166746786182 2280998753949 4461632979717 8731188863470
17094432576778 33483379603407 65612899915304
128625503610475))
(define vecA062692 (vector 0 2 3 5 8 14 23 41 71 127 226 412 747 1377 2538 4720
8800 16510 31042 58636 111013 210871 401428 766150 1465020
2807196 5387991 10358999 19945394 38458184 74248451
143522117 277737797 538038783 1043325198))
(define (A007053 n) (vector-ref vecA007053 n))
(define (A062692 n) (vector-ref vecA062692 n))
(define (A007053v2 n) (A000720 (A000079 n)))
(define (A062692v2 n) (A091226 (A000225 (+ n 1))))
;; Intersect of A014580 & A000040.
;; Compare to A027697: Primes with odd number of 1's in their binary expansion. ???
;; (C.f. A027698).
;; Note that all elements of A014580 (except 3) seem to have an odd number of 1's in their binary expansion!
;; (thus also this and A091214)
(define (A091206 n) (A000040 (A091207 n)))
;; Positions of intersect of A014580 & A000040 in A000040:
;; One-based. Complement of A091210.
(definec (A091207 n)
(cond
((<= n 1) n)
(else
(let loop ((i (+ 1 (A091207 (- n 1)))))
(cond ((= (A091225 (A000040 i)) 1) i)
(else (loop (+ 1 i)))
)
)
)
)
)
;; Positions of intersect of A014580 & A000040 in A014580:
;; One-based. Complement of A091215.
(definec (A091208 n)
(cond
((<= n 1) n)
(else
(let loop ((i (+ 1 (A091208 (- n 1)))))
(cond ((= (A010051 (A014580 i)) 1) i)
(else (loop (+ 1 i)))
)
)
)
)
)
;; Set-wise difference of A000040 & A014580 i.e. intersect of A000040 & A091242
;; (i.e. those primes which are composite when inteprereted as GF2[X] polynomials).
(define (A091209 n) (A000040 (A091210 n)))
;; Positions of A091209 in A000040:
;; One-based. Complement of A091207.
(definec (A091210 n)
(cond
((= 1 n) 3) ;; p3 = 5 is the first prime, which when intepreted as 101 = x^2 + 1 = (x+1)^2 is not irreducible.
(else
(let loop ((i (+ 1 (A091210 (- n 1)))))
(cond ((= (A091225 (A000040 i)) 0) i)
(else (loop (+ 1 i)))
)
)
)
)
)
;; Positions of A091209 in A091242:
;; One-based. Complement of A091213.
(definec (A091211 n)
(cond
((= 1 n) 2) ;; position of 5 in A091242 is 2.
(else
(let loop ((i (+ 1 (A091211 (- n 1)))))
(cond ((= (A010051 (A091242 i)) 1) i)
(else (loop (+ 1 i)))
)
)
)
)
)
;; Intersect of A091242 & A002808. I.e. composites in both domains.
(define (A091212 n) (A091242 (A091213 n)))
;; Positions of intersect of A091242 & A002808 in A091242:
;; One-based. Complement of A091211.
(definec (A091213 n)
(cond
((<= n 1) n) ;; 4 is the first composite, in both.
(else
(let loop ((i (+ 1 (A091213 (- n 1)))))
(cond ((= (A066247 (A091242 i)) 1) i)
(else (loop (+ 1 i)))
)
)
)
)
)
;; Set-wise difference of A014580 & A000040 i.e. intersect of A014580 & A002808
;; (i.e. those irreducible GF2[X] polynomials which are composites in N).
(define (A091214 n) (A014580 (A091215 n)))
;; Positions of A091214 in A014580:
;; One-based. Complement of A091208.
(definec (A091215 n)
(cond
((= 1 n) 7) ;; A014580(7) = 25 is the first irreducible which is not prime.
(else
(let loop ((i (+ 1 (A091215 (- n 1)))))
(cond ((= (A066247 (A014580 i)) 1) i)
(else (loop (+ 1 i)))
)
)
)
)
)
(define (A091219 n) ;; Moebius mu
(cond ((not (= (A091221 n) (A091222 n))) 0) ;; Well, contains a square!
(else (expt -1 (A091222 n)))
)
)
;; A091220 is analogous to A000005: tau(n): number of divisors of n.
(definec (A091220 n) (apply * (map 1+ (multiplicities (GF2Xfactor n)))))
;; A091221 is analogous to A001221: Number of distinct primes dividing n.
;; (omega(n))
;; A091222 is analogous to A001222: Number of prime divisors of n
;; (with multiplicity). Also called (bigomega(n) or Omega(n)).
;; A091223 is analogous to A001223: Differences between consecutive primes.
;; i.e. the first differences of A014580.
(define (A091221 n) (distinct-elems (GF2Xfactor n)))
(define (A091222 n) (length (GF2Xfactor n)))
(definec (A091223 n)
(cond ((= n 1) n)
(else
(let loop ((i (1+ (A014580 n))))
(cond ((= 1 (A091225 i)) (- i (A014580 n)))
(else (loop (+ 1 i)))
)
)
)
)
)
;; A091224 is analogous to A028334: Differences between consecutive primes,
;; divided by 2. Starts from offset 2:
(define (A091224 n) (/ (A091223 n) 2))
;; A014580 is analogous to A000040 (primes). I think it should be 1-based!
;; 2,3,7,11,13,19,25,31,37,41,47,55,59,61,67,73,87,91,97,103,
;; Note: (a014580 4720) = 65533
(definec (A014580 n)
(cond ((<= n 2) (+ 1 n))
(else (+ (A014580 (- n 1)) (A091223 (- n 1))))
)
)
;; A091225 is analogous to A010051:
;; Characteristic function of primes: 1 if n is prime else 0.
(define (A091225 n)
(if (= 1 (length (GF2Xfactor n))) 1 0)
)
;; A091226 is analogous to A000720: pi(n), the number of primes <= n.
;; i.e. partial sums of the corresponding characteristic function.
(definec (A091226 n)
(cond ((< n 2) 0)
(else (+ (A091225 n) (A091226 (- n 1))))
)
)
;; A091227 is analogous to A049084: 0 unless n is a prime p(k) when a(n) = k.
(definec (A091227 n) (* (A091225 n) (A091226 n)))
;; A091228 is analogous to A007918 Smallest prime >= n. I.e. gives the next irreducible n.
(definec (A091228 n)
(cond
((<= n 2) 2)
((>= (A091228 (- n 1)) n) (A091228 (- n 1))) ;; Optimizes as this is cached function.
(else ;; Find next irreducible one.
(let loop ((i n))
(cond ((= 1 (A091225 i)) i)
(else (loop (+ 1 i)))
)
)
)
)
)
;; A091229 is analogous to A007920 Smallest k such that n+k is prime. (Smarandache complementary prime function) a(n) = A007918(n) - n.
(define (A091229 n) (- (A091228 n) n))
;; An analog for the primeth recurrence:
(definec (A091230 n) (if (zero? n) 1 (A014580 (A091230 (- n 1)))))
;; How many more primes there are in range [0,2^n] in total than GF(2)[X]-irreducibles:
;; (0 0 0 1 1 3 4 8 13 26 45)
;; Compute also the first differences.
(define (A091231 n)
(if (< n 2)
0
(- (A007053 n) (A062692 (- n 1)))
)
)
(define (A091231v2 n)
(if (< n 2)
0
(- (A007053v2 n) (A062692v2 (- n 1)))
)
)
;; There are saner ways to count this! Use A001037
;; A001037 1,2,1,2,3,6,9,18,30,56,99,186,335,630,1161,2182,4080,7710,14532,27594, (offset 0)
;; A036378 = 1,1,2,2,5,7,13,23,43,75,137,255,464,872,1612,3030,5709,10749,20390, (offset 1.)
;; (0 0 1 0 2 1 4 5 13 19 38)
;; How many more primes there are in range [2^n,2^(n+1)] than GF(2)[X]-irreducibles:
;; Offset 0.
(define (A091232 n) (- (A091231 (+ 1 n)) (A091231 n))) ;; Upto n=34
(define (A091232v2 n) (if (< n 2) 0 (- (A036378 (+ n 1)) (A001037 n)))) ;; upto n=18.
;; Compare to A091241:
(define (A091233 n) (1+ (- (A005518 n) (A005517 n))))
;; A091242 is analogous to A002808 (composites). I think it should be 1-based!
(definec (A091242 n)
(cond ((= n 1) 4)
(else (+ (A091242 (- n 1)) (A091243 (- n 1))))
)
)
;; Both offset=1:
;; A091243 is analogous to A073783: Differences between composite numbers.
(definec (A091243 n)
(cond ((= n 1) 1)
(else
(let loop ((i (1+ (A091242 n))))
(cond ((= 1 (A091247 i)) (- i (A091242 n)))
(else (loop (+ 1 i)))
)
)
)
)
)
;; A091244 is analogous to A073784: Number of primes between successive composites.
(define (A091244 n) (- (A091243 n) 1))
;; A091245 is analogous to A065855: number of composites <= n.
;; i.e. partial sums of the corresponding characteristic function.
(definec (A091245 n)
(cond ((< n 4) 0)
(else (+ (A091247 n) (A091245 (- n 1))))
)
)
;; A091246 is analogous to A066246: 0 unless n is a composite, otherwise its index.
(definec (A091246 n) (* (A091247 n) (A091245 n)))
;; A091247 is analogous to A066247 (characteristic function of composites)
(define (A091247 n) (if (and (> n 3) (zero? (A091225 n))) 1 0))
;; Here we are computing the primitive polynomials in very straightforward way,
;; as adapted from: http://mathworld.wolfram.com/PrimitivePolynomial.html
;; and: http://mathworld.wolfram.com/PolynomialOrder.html
;; There are probably cleverer ways of computing these,
;; see e.g.
;; http://www.theory.csc.uvic.ca/~cos/inf/neck/PolyInfo.html
(define (A000374 n) (distinct-elems (Xn_1factor n)))
(define (A091248 n) (length (Xn_1factor n)))
;; The first x^n + 1 polynomial where the nth irreducible GF(2)[X] -polynomial
;; is found as a factor, 0 if never.
;; In OEIS given with name:
;; Arrange irreducible polynomials over GF(2) in lexicographic order
;; and write down the order of each polynomial.
;; with a(1)=1, instead of 0.
(definec (A059478 n)
(let ((p (A014580 n)))
(cond ((= 1 n) 1)
(else (let loop ((i 1))
(if (member p (Xn_1factor i))
i
(loop (+ 1 i))
)
)
)
)
)
)
;; Give the positions of primitive GF(2)[X]-polynomials in A014580:
;; (map A014580 (iota 10)) --> (2 3 7 11 13 19 25 31 37 41)
;; (map A059478 (iota 10)) --> (1 1 3 7 7 15 15 5 31 31)
;; (map A000523 (map A014580 (iota 10))) --> (1 1 2 3 3 4 4 4 5 5)
(definec (A091249 n)
(cond
((= n 1) 2) ;; The first primitive is A014580[2] = 3 = x+1.
(else
(let loop ((i (+ 1 (A091249 (- n 1)))))
(cond ((equal? (A059478 i) (A000225 (A000523 (A014580 i)))) i)
(else (loop (+ 1 i)))
)
)
)
)
)
(define (A091250 n) (A014580 (A091249 n)))
(define (A058947 n) (A007088 (A091250 n)))
;; A058947 = A007088(A091250(n))
;; Give the positions of non-primitive GF(2)[X]-polynomials in A014580:
(definec (A091251 n)
(cond
((= n 1) 1) ;; The first non-primitive is A014580[1] = 2 = x.
(else
(let loop ((i (+ 1 (A091251 (- n 1)))))
(cond ((not (equal? (A059478 i) (A000225 (A000523 (A014580 i))))) i)
(else (loop (+ 1 i)))
)
)
)
)
)
(define (A091252 n) (A014580 (A091251 n)))
(define (A091253 n) (A007088 (A091252 n)))
(define (A091254 n) (A007088 (A091242 n)))
;;
(define A004247bi *)
(define (A004247 n) (* (A002262 n) (A025581 n)))
;; A048720 is analogous to A004247 (the ordinary multiplication table):
;; Let's use Henry Bottomley's formula:
;; T(2b,c)=T(c,2b)=T(b,2c)=2T(b,c); T(2b+1,c)=T(c,2b+1)=2T(b,c) XOR c
(define (A048720bi x y)
(cond ((zero? x) 0)
((zero? y) 0)
((even? x) (* 2 (A048720bi (/ x 2) y)))
(else (A003987bi (* 2 (A048720bi (/ (- x 1) 2) y)) y))
)
)
(define (A048720 n) (A048720bi (A002262 n) (A025581 n)))
;; Analogous to A003991:
;; One-based variant of A048720, that's why the calisthenics with the indices:
(define (A091257 n) (A048720bi (1+ (A002262 (-1+ n))) (1+ (A025581 (-1+ n)))))
(define (A001317 n)
(fold-left a048720bi 1 (map (lambda (x) 3) (iota n)))
)
;; Analogous to A003989, GCD.
(define (A091255bi x y)
(fold-left a048720bi 1 (m-intersect (GF2Xfactor x) (GF2Xfactor y)))
)
;; Analogous to A003990, LCM.
(define (A091256bi x y)
(fold-left a048720bi 1 (m-union (GF2Xfactor x) (GF2Xfactor y)))
)
;; Note that it is one-based, that's why the calisthenics with the indices:
(define (A091255 n) (A091255bi (1+ (A002262 (-1+ n))) (1+ (A025581 (-1+ n)))))
(define (A091256 n) (A091256bi (1+ (A002262 (-1+ n))) (1+ (A025581 (-1+ n)))))
;; One way to check that we are doing it right:
;; X*Y = GCD(X,Y)*LCM(X,Y)
;; (equal? (map A091257v2 (iota 2048)) (map A091257 (iota 2048))) --> #t
(define (A091257v2 n) (A048720bi (A091255 n) (A091256 n)))
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; ;;
;; Output functions and check lists. ;;
;; ;;
;; Note: I should make this a separate module of its own, ;;
;; available under http://www.research.att.com/~njas/sequences/format.html ;;
;; say with the name: ;;
;; http://www.research.att.com/~njas/sequences/formatSC.txt ;;
;; for all OEIS-Scheme-hackers to enjoy. ;;
;; ;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; Call e.g. as:
;; (map check-entry10 GF2Xfuns_list)
;; (map check-entry25 GF2Xfuns_list)
;; (map check-entry55 GF2Xfuns_list)
;;
;; Or:
;; (output-entries-to-file GF2Xfuns_list "A91202-57.seqs" "Jan 03 2004")
(define GF2Xfuns_list
(list
;; Here just for checking that certain permutations are inverses of each other:
(list 001477 "Non-negative integers, identity permutation in S_inf."
'(off: 0)
'(indentries: Nperm)
'(comps: (091202 091203) (091203 091202) (091204 091205) (091205 091204))
)
(list 000040 "Prime numbers, irreducible elements in domain of natural numbers."
'(off: 1)
'(comps: (091203 014580))
'(inv: 049084)
'(y: "Union of A091206 & A091209.")
)
(list 049084 "Inverse function of A000040: position in A000040 if n is prime, 0 otherwise."
'(off: 1)
'(comps: (091227 091202))
'(inv: 000040)
)
(list 001221 "omega(n): Number of distinct primes dividing n."
'(off: 1)
'(comps: (091221 091202) (091221 091204))
)
(list 001222 "bigomega(n): Number of prime divisors of n (counted with multiplicity)."
'(off: 1)
'(comps: (091222 091202) (091222 091204))
)
(list 014580 "Irreducible GF(2)[X]-polynomials."
'(off: 1)
'(inv: 091227)
'(comps: (091202 000040))
'(indentries: GF2X)
'(y: "Almost complement of A091242. Union of A091206 & A091214, and also of A091250 & A091252. First differences: A091223.")
)
(list 091202 "Multiplicative isomorphism from integers to GF2X-polynomials."
'(off: 0)
'(indentries: GF2X Nperm)
'(inv: 091203)
)
(list 091203 "Multiplicative isomorphism from GF2X-polynomials to integers."
'(off: 0)
'(indentries: GF2X Nperm)
'(inv: 091202)
)
(list 091204 "Deeply multiplicative isomorphism from integers to GF2X-polynomials."
'(off: 0)
'(upto: 256)
'(indentries: GF2X Nperm)
'(keywords: "nice") ;; This deserves it!
'(comps: (91227 091204 000040))
'(inv: 091205)
)
(list 091205 "Deeply multiplicative isomorphism from GF2X-polynomials to integers."
'(off: 0)
'(upto: 256)
'(indentries: GF2X Nperm)
'(keywords: "nice") ;; This deserves it!
'(comps: (049084 091205 014580))
'(inv: 091204)
)
(list 091206 "Primes that are also irreducible GF(2)[X]-polynomials."
'(off: 1)
'(comps: (000040 091207) (014580 091208))
'(y: "Intersect of A014580 & A000040. Apart from a(2)=3 a subset of A027697.")
'(indentries: GF2X)
)
(list 091207 "Indices of primes that are also irreducible GF(2)[X]-polynomials."
'(off: 1)
'(comps: (049084 091206))
'(y: "Complement of A091210.")
)
(list 091208 "A014580-indices of irreducible GF(2)[X]-polynomials that are also primes."
'(off: 1)
'(comps: (091227 091206))
'(y: "Complement of A091215.")
)
(list 091209 "Primes that are composite GF(2)[X]-polynomials."
'(off: 1)
'(comps: (000040 091210) (091242 091211))
'(y: "Intersect of A000040 and A091242.")
'(indentries: GF2X)
)
(list 091210 "Indices of primes that are composite GF(2)[X]-polynomials."
'(off: 1)
'(comps: (049084 091209))
'(y: "Complement of A091207.")
'(indentries: GF2X)
)
(list 091211 "A091242-indices of primes that are composite GF(2)[X]-polynomials."
'(off: 1)
'(comps: (091246 091209))
'(y: "Complement of A091213.")
'(indentries: GF2X)
)
(list 091212 "Composite GF(2)[X]-polynomials that are also composite integers."
'(off: 1)
'(comps: (091242 091213))
'(y: "Intersect of A002808 and A091242.")
'(indentries: GF2X)
)
(list 091213 "A091242-indices of composite GF(2)[X]-polynomials that are also composite integers."
'(off: 1)
'(comps: (091246 091212))
'(y: "Complement of A091211.")
'(indentries: GF2X)
)
(list 091214 "Irreducible GF(2)[X]-polynomials that are composite integers."
'(off: 1)
'(comps: (014580 091215))
'(y: "Intersect of A002808 and A014580.")
'(indentries: GF2X)
)
(list 091215 "A014580-indices of irreducible GF(2)[X]-polynomials that are composite integers."
'(off: 1)
'(comps: (091227 091214))
'(y: "Complement of A091208.")
)
(list 091219 "Moebius-analog for the domain GF(2)[X]: a(n)=0 if A091221(n)!=A091222(n), otherwise -1^A091222(n)."
'(off: 1)
'(comps: (008683 091203) (008683 091205))
'(indentries: GF2X)
)
(list 091220 "Number of divisors in the nth GF(2)[X]-polynomial."
'(off: 1)
'(comps: (000005 091203) (000005 091205))
'(indentries: GF2X)
)
(list 091221 "Number of distinct irreducible polynomials dividing nth GF(2)[X]-polynomial."
'(off: 1)
'(comps: (001221 091203) (001221 091205))
'(indentries: GF2X)
'(y: "A000374(n) = a(A000051(n)).")
)
(list 091222 "Number of irreducible polynomials dividing nth GF(2)[X]-polynomial. (counted with multiplicity)."
'(off: 1)
'(comps: (001222 091203) (001222 091205))
'(indentries: GF2X)
'(y: "A091248(n) = a(A000051(n)).")
)
(list 091223 "Differences between consecutive irreducible GF(2)[X]-polynomials."
'(off: 1)
'(c: "Analogous to A001223.")
'(y: "First differences of A014580. Divided by 2: A091224.")
'(indentries: GF2X)
)
(list 091224 "Differences between consecutive irreducible GF(2)[X]-polynomials, divided by 2."
'(off: 2)
'(c: "Analogous to A028334.")
'(y: "a(n) = A091223(n)/2.")
)
(list 091225 "Characteristic function of A014580: 1 if the nth GF(2)[X] polynomial is irreducible, 0 otherwise."
'(off: 0)
'(comps: (010051 091203) (010051 091205))
'(y: "Partial sums give A091226. Cf. A091227. Complementary to A091247.")
'(indentries: GF2X)
)
(list 091226 "Number of irreducible GF(2)[X]-polynomials in range [0,n]."
'(off: 0)
'(c: "Analogous to A000720.")
'(y: "Partial sums of A091225. A062692(n) = a(2^n).")
'(indentries: GF2X)
)
(list 091227 "Inverse function of A014580: position in A014580 if the nth GF(2)[X] polynomial is irreducible, 0 otherwise."
'(off: 1)
'(comps: (049084 091203))
'(inv: 014580)
'(f: "a(n) = A091225(n) * A091226(n).")
'(indentries: GF2X)
)
(list 091228 "Smallest m >= n, such that m is irreducible when interpreted as GF(2)[X]-polynomial."
'(off: 0)
'(f: "a(n) = n + A091229(n).")
'(c: "Analogous to A007918.")
'(indentries: GF2X)
)
(list 091229 "Smallest k such that n+k is irreducible when interpreted as GF(2)[X]-polynomial."
'(off: 0)
'(f: "a(n) = A091228(n) - n.")
'(c: "Analogous to A007920.")
)
(list 091230 "Iterates of A014580."
'(off: 0)
'(upto: 7) ;; Grows so fast, compute only up to 7. (1 2 3 7 25 137 1123 13103)
'(f: "a(0)=1, a(n) = A014580(a(n-1)).")
'(y: "A091238(a(n)) = n+1.")
'(comps: (091204 007097))
'(indentries: GF2X)
)
(list 091231 "How many more primes than irreducible GF(2)[X] polynomials there are in range [0,2^n]."
'(off: 0)
'(upto: 34)
'(indentries: GF2X)
'(f: "a(0)=a(1)=0, a(n) = A007053(n)-A062692(n-1).")
'(y: "Partial sums of A091232.")
)
(list 091232 "How many more primes than irreducible GF(2)[X] polynomials there are in range [2^n,2^(n+1)]."
'(off: 0)
'(upto: 34)
'(indentries: GF2X)
'(f: "a(0)=a(1)=0, a(n) = A036378(n+1)-A001037(n).")
'(y: "First differences of A091231.")
)
(list 091233 "Size of range [Smallest Matula number coding a tree of n nodes,Largest Matula number coding a tree of n nodes]."
'(off: 1)
'(upto: 16)
'(f: "a(n) = (A005518(n)-A005517(n))+1.")
'(y: "Compare to A091241.")
)
(list 091238 "Number of nodes in rooted tree with GF2X-Matula number n."
'(off: 1)
'(c: "Each n occurs A000081(n) times.")
'(y: "a(A091230(n)) = n+1. Cf. A091239-A091241.")
'(comps: (061775 091205))
)
(list 091239 "Smallest GF2X-Matula number i with number of nodes = n in the corresponding tree."
'(off: 1)
'(upto: 31)
'(y: "Analogous to A005517. A091240 gives the largest i with number of nodes = n. Cf. A091241.")
)
(list 091240 "Largest GF2X-Matula number i with number of nodes = n in the corresponding tree."
'(off: 1)
'(upto: 8)
'(c: "Apparently from n=4 onward given by recurrence a(4)=A014580(4), a(5)=A014580(A014580(4)), a(6)=A014580(A014580(A014580(4))), etc.")
'(y: "Analogous to A005518. A091239 gives the smallest i with number of nodes = n. Cf. A091241.")
)
(list 091241 "Size of range [Smallest GF2X-Matula number coding a tree of n nodes,Largest GF2X-Matula number coding a tree of n nodes]."
'(off: 1)
'(upto: 8)
'(f: "a(n) = (A091240(n)-A091239(n))+1.")
'(y: "Compare to A091233.")
)
(list 091242 "Reducible GF(2)[X]-polynomials."
'(off: 1)
'(inv: 091246)
'(indentries: GF2X)
'(c: "Analogous to A002808.")
'(y: "Almost complement of A014580. Union of A091209 & A091212. First differences: A091243. Characteristic function: A091247. In binary format: A091254.")
)
(list 091243 "Differences between consecutive reducible GF(2)[X]-polynomials."
'(off: 1)
'(c: "Analogous to A073783.")
'(y: "First differences of A091242. a(n) = A091244(n)+1.")
'(indentries: GF2X)
)
(list 091244 "Number of irreducible polynomials between successive reducible GF(2)[X]-polynomials."
'(off: 1)
'(c: "Analogous to A073784.")
'(y: "a(n) = A091243(n)-1.")
'(indentries: GF2X)
)
(list 091245 "Number of reducible GF(2)[X]-polynomials in range [0,n]."
'(off: 0)
'(c: "Analogous to A065855.")
'(y: "Partial sums of A091247.")
'(indentries: GF2X)
)
(list 091246 "Inverse function of A091242: position in A091242 if the nth GF(2)[X] polynomial is reducible, 0 otherwise."
'(off: 1)
'(inv: 091242)
'(c: "Analogous to A066246.")
'(f: "a(n) = A091245(n) * A091247(n).")
'(indentries: GF2X)
)
(list 091247 "Characteristic function of A091242: 1 if the nth GF(2)[X] polynomial is composite, 0 otherwise."
'(off: 0)
'(comps: (066247 091203) (066247 091205))
'(y: "Complementary to A091225. Partial sums give A091245. Cf. A091246")
'(indentries: GF2X)
)
(list 091248 "Number of irreducible factors in the factorization of GF(2)[X]-polynomial x^n+1 (counted with multiplicity)."
'(off: 1)
'(upto: 120)
'(c: "Cf. A000374")
'(f: "a(n) = A091222(A000051(n)).")
;; '(comps: (091222 000051))
'(indentries: GF2X)
)
(list 091249 "A014580-indices of primitive irreducible GF(2)[X]-polynomials."
'(off: 1)
'(upto: 100)
'(comps: (091227 091250))
'(y: "Complement of A091251.")
'(indentries: GF2X)
)
(list 091250 "Primitive irreducible polynomials over GF(2)."
'(off: 1)
'(upto: 100)
'(comps: (014580 091249))
'(y: "Cf. A011260, A091252. A058947(n) = A007088(a(n)).")
'(indentries: GF2X)
)
(list 091251 "A014580-indices of non-primitive irreducible GF(2)[X]-polynomials."
'(off: 1)
'(upto: 27)
'(comps: (091227 091252))
'(y: "Complement of A091249.")
'(indentries: GF2X)
)
(list 091252 "Non-primitive irreducible polynomials over GF(2)."
'(off: 1)
'(upto: 27)
'(comps: (014580 091251))
'(y: "Cf. A091250. In binary format: A091253.")
'(indentries: GF2X)
)
(list 091253 "Non-primitive irreducible polynomials over GF(2), in binary format."
'(off: 1)
'(upto: 27)
'(comps: (007088 091252))
'(indentries: GF2X)
)
(list 091254 "Reducible polynomials over GF(2), in binary format."
'(off: 1)
'(comps: (007088 091242))
'(y: "Cf. A058943.")
'(indentries: GF2X)
)
(list 091255 "Table of GCD(x,y) computed for polynomials over GF(2), where (x,y) runs as (1,1),(1,2),(2,1),(1,3),(2,2),(3,1),..."
'(off: 1)
'(keywords: "tabl")
'(c: "Analogous to A003989.")
'(y: "Cf. A091256, A091257.")
'(indentries: GF2X Lattices)
)
(list 091256 "Table of LCM(x,y) computed for polynomials over GF(2), where (x,y) runs as (1,1),(1,2),(2,1),(1,3),(2,2),(3,1),..."
'(off: 1)
'(keywords: "tabl")
'(c: "Analogous to A003990.")
'(y: "Cf. A091255, A091257.")
'(indentries: GF2X Lattices)
)
(list 091257 "Multiplication table A x B computed for polynomials over GF(2), where (A,B) runs as (1,1),(1,2),(2,1),(1,3),(2,2),(3,1),..."
'(off: 1)
'(keywords: "tabl")
'(c: "Essentially same as A048720 but computed starting from offset one instead of zero. Analogous to A003991.")
'(y: "a(n) = A048720bi(A091255(n),A091256(n)), because A x B = GCD(A,B) x LCM(A,B) holds also in the polynomial ring GF(2)[X].")
'(indentries: GF2X)
)
(list 061775 "Number of nodes in rooted tree with Matula-Goebel number n."
'(off: 1)
'(c: "Each n occurs A000081(n) times.")
'(comps: (091238 091204))
)
)
)
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; ;;
;; Copied and modified from: ;;
;; http://www.iki.fi/~kartturi/matikka/Nekomorphisms/gato-out.scm ;;
;; functions output-gatomorphism-entry-aux et al. ;;
;; ;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
(load-option 'format)
(define (Anum->str Anum)
(string-append "A"
(string-pad-left (if (string? Anum) Anum (number->string Anum)) 6 #\0)
)
)
(define output_seq
(lambda (seq)
(cond ((null? seq)) ;; No (newline) this time!
(else (write (car seq))
(if (not (null? (cdr seq))) (write-string ","))
(output_seq (cdr seq))
)
)
)
)
(define (len-of-max-full-line-prefix seq max-line-len)
(let loop ((seq seq)
(terms 0)
(room-left max-line-len)
)
(cond ((negative? room-left) (max 1 (- terms 1))) ;; At least one term, even if it is overlength!
((not (pair? seq)) terms)
(else (loop (cdr seq)
(+ 1 terms)
(- room-left (string-length (format #f ",~A" (car seq))))
)
)
)
)
)
(define (html-out-sequence-search-link out seq seeklen)
(with-output-to-port out
(lambda ()
(let ((seek-seq (cond ((< seeklen (- (length seq) 2)) (list-head (cddr seq) seeklen)) (else (cddr seq)))))
(write-string "")
(output_seq (list-head seq (min seeklen (length seq))))
(write-string "\n")
)
)
)
)
(define (html-out-Anchor Anum out)
(format out "" (Anum->str Anum))
)
(define (html-out-sequence-A-link Anum out)
(let ((Astr (Anum->str Anum)))
(format out "~A" Astr Astr)
)
)
;; Works in MIT Scheme:
(define (Anum->Afun Anum)
(eval (string->symbol (string-downcase (Anum->str Anum))) user-initial-environment)
)
;; (complist->exprstr (list 1 2 3 4)) --> "A000001(A000002(A000003(A000004(n))))"
(define (complist->exprstr complist)
(with-string-output-port
(lambda (outport)
(for-each (lambda (anum) (format outport "~A(" (Anum->str anum)))
complist
)
(format outport "n")
(for-each (lambda (x) (format outport ")")) complist)
)
)
)
(define (check-composition outport comp base-seq Aseq Astr check-only?)
(let ((Acomp (compose-funlist (map Anum->Afun comp))))
(cond ((not (equal? (map Acomp base-seq) Aseq))
(format outport "!!! The composition ~A = ~A is not correct!\n"
Astr (complist->exprstr comp)
)
)
(check-only?
(format outport "Yes, the composition ~A = ~A is correct.\n"
Astr (complist->exprstr comp)
)
)
)
)
)
(define (check-entry10 listlet) (output-OEIS-entry listlet 1024 10 #t "Kuu 00 2004" (current-output-port)))
(define (check-entry25 listlet) (output-OEIS-entry listlet 1024 25 #t "Kuu 00 2004" (current-output-port)))
(define (check-entry55 listlet) (output-OEIS-entry listlet 1024 45 #t "Kuu 00 2004" (current-output-port)))
(define (output-entries-to-file listlets outfile subm-date)
(call-with-output-file outfile
(lambda (outport)
(map (lambda (listlet) (output-OEIS-entry listlet 120 45 #f subm-date outport))
listlets
)
)
)
)
(define (output-OEIS-entry listlet check-upto-n seek-len check-only? subm-date outport)
(let* ((Anum (list-ref listlet 0))
(name (list-ref listlet 1))
(rest-of (cddr listlet))
(c (cond ((assoc 'c: rest-of) => cadr) (else #f)))
(f (cond ((assoc 'f: rest-of) => cadr) (else #f)))
(y (cond ((assoc 'y: rest-of) => cadr) (else #f)))
(off (cond ((assoc 'off: rest-of) => cadr) (else (error "output-entry: field 'off:' (starting offset) required!"))))
(keywords (cond ((assoc 'keywords: rest-of) => cadr) (else #f)))
(Ainv (cond ((assoc 'inv: rest-of) => cadr) (else #f)))
(comps (cond ((assoc 'comps: rest-of) => cdr) (else #f))) ;; '(comps: (000040 091207) (014580 091208))
(scheme (cond ((assoc 'scheme: rest-of) => cdr) (else #f)))
(indentries (cond ((assoc 'indentries: rest-of) => cdr) (else (list))))
(check-only? (or check-only? (assoc 'check-only! rest-of)))
(check-upto-n (cond ((assoc 'upto: rest-of) => cadr) (else check-upto-n)))
(Astr (Anum->str Anum))
(Afun (Anum->Afun Anum))
(Ainvstr (and Ainv (Anum->str Ainv)))
(Ainvfun (and Ainv (Anum->Afun Ainv)))
(base-seq (map (lambda (n) (+ n off)) (iota0 (- check-upto-n off))))
(Aseq (map Afun base-seq))
(negative-terms? (there-exists? Aseq negative?))
(one-based-pos-of-first-term-gte-2
(cond ((pos-of-first-matching Aseq (lambda (x) (>= (abs x) 2))) => 1+)
(else 1) ;; If no terms other than 0,1 or -1, then use 1 as the second elem of offset pair.
)
)
(more-than-one-zero? (cond ((and Ainvfun (memq 0 Aseq)) => (lambda (r) (memq 0 (cdr r)))) (else #f)))
;; (no-larger-than-abs-1-terms? (for-all? Aseq (lambda (n) (< (abs n) 2)))) ;; Not needed.
(Y-line-started? #f) ;; Not yet.
)
(cond (Ainvfun
;; If Aseq has more than one 0, then the given inverse function is non-surjective injection from N to N,
;; and we have to check Afun(Ainvfun(x)), and otherwise Ainvfun(Afun(x)):
(cond (more-than-one-zero?
(let ((Ainvseq (map Ainvfun base-seq)))
(cond ((not (equal? (map Afun Ainvseq) base-seq))
(format outport "!!! This function ~A IS NOT an inverse function of injection ~A (checked up to n=~A).\n"
Astr Ainvstr
)
)
(check-only?
(format outport "Yes, this function ~A seems to be an inverse function of non-surjective injection ~A (checked up to n=~A).\n"
Astr Ainvstr check-upto-n
)
)
)
) ;; let
)
((not (equal? (map Ainvfun Aseq) base-seq))
(format outport "!!! The inverse ~A for ~A is not correct\n"
Ainvstr Astr
)
)
(check-only?
(format outport "Yes, function ~A seems to be an inverse of ~A when computed up to n=~A\n"
Ainvstr Astr check-upto-n
)
)
)
)
)
(cond (comps
(for-each (lambda (comp)
(check-composition outport comp base-seq Aseq Astr check-only?)
)
comps
)
)
)
(cond (check-only?
(html-out-sequence-A-link Anum outport)
(format outport " = \n")
(html-out-sequence-search-link outport Aseq seek-len)
)
(else
(format outport "%I ~A\n" Astr)
(let* ((max-term-line-len 69) ;; As (string-length "%S A012345") = 10.
(part1len (len-of-max-full-line-prefix Aseq max-term-line-len))
(part2len (len-of-max-full-line-prefix (list-tail Aseq part1len) max-term-line-len)) ;; Could be zero!
(part3len (len-of-max-full-line-prefix (list-tail Aseq (+ part1len part2len)) max-term-line-len)) ;; Could be zero!
(part1 (sublist Aseq 0 part1len))
(part2 (sublist Aseq part1len (+ part1len part2len))) ;; results () if part2len = 0.
(part3 (sublist Aseq (+ part1len part2len) (+ part1len part2len part3len))) ;; results () if part2len = 0 or part3len = 0.
)
(with-output-to-port outport
(lambda ()
(format outport "%S ~A " Astr) (output_seq (map abs part1)) (format outport ",\n")
(cond ((pair? part2)
(format outport "%T ~A " Astr) (output_seq (map abs part2)) (format outport ",\n")
)
)
(cond ((pair? part3)
(format outport "%U ~A " Astr) (output_seq (map abs part3)) (newline outport)
)
)
(cond (negative-terms?
(format outport "%V ~A " Astr) (output_seq part1) (format outport ",\n")
(cond ((pair? part2)
(format outport "%W ~A " Astr) (output_seq part2) (format outport ",\n")
)
)
(cond ((pair? part3)
(format outport "%X ~A " Astr) (output_seq part3) (newline outport)
)
)
)
)
)
)
) ;; let*
(format outport "%N ~A ~A\n" Astr name)
(cond (f
(format outport "%F ~A ~A\n" Astr f)
)
)
(cond (c
(format outport "%C ~A ~A\n" Astr C)
)
)
(format outport "%H ~A A. Karttunen, Scheme-program for computing this sequence.\n"
Astr
)
(cond
((pair? indentries)
(cond ((memq 'GF2X indentries)
(format outport "%H ~A Index entries for sequences operating on GF(2)[X]-polynomials\n"
Astr
)
)
)
(cond ((memq 'Lattices indentries)
(format outport "%H ~A Index entries for sequences related to Lattices\n"
Astr
)
)
)
(cond ((memq 'Nperm indentries)
(format outport "%H ~A Index entries for sequences that are permutations of the natural numbers\n"
Astr
)
)
)
)
)
(cond (Ainv
(cond ((not Y-line-started?)
(format outport "%Y ~A" Astr)
(set! Y-line-started? #t)
)
)
(cond (more-than-one-zero?
(format outport " Inverse of ~A." Ainvstr)
)
(else
(format outport " Inverse: ~A." Ainvstr)
)
)
)
)
;; We should also check them, but can't do this with just A-numbers, as
;; we need the function definitions. (Here the old-fashioned Lisp would beat Scheme.)
(cond (comps
(cond ((not Y-line-started?)
(format outport "%Y ~A" Astr)
(set! Y-line-started? #t)
)
)
(format outport " a(n)")
(for-each (lambda (comp)
(format outport " = ~A" (complist->exprstr comp))
)
comps
)
(format outport ".")
)
)
(cond (y
(cond ((not Y-line-started?)
(format outport "%Y ~A" Astr)
(set! Y-line-started? #t)
)
)
(format outport " ~A" y)
)
)
(if Y-line-started? (newline outport))
(format outport "%K ~A ~A~A\n"
Astr (if negative-terms? "sign" "nonn")
(if keywords (string-append "," keywords) "")
)
(format outport "%O ~A ~A,~A\n"
Astr off one-based-pos-of-first-term-gte-2
)
(format outport "%A ~A Antti Karttunen (His-Firstname.His-Surname(AT)iki.fi), ~A\n"
Astr subm-date
)
(cond (scheme
(format outport "%o ~A (MIT Scheme:)\n" Astr)
(for-each (lambda (schemedef) (format outport "%o ~A ~A\n" Astr schemedef)) scheme)
)
)
(newline outport)
) ;; else
) ;; cond
) ;; let*
)
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; ;;
;; The following C++ program has been used to precompute the vectors ;;
;; GF2X_FACVEC and Xn_1_FACVEC used in this Scheme-program. ;;
;; After compiling the program I have performed ;;
;; GF2Xfacs 65536 > GF2Xfacv.scm ;;
;; and ;;
;; GF2Xfacs -511 > Xn_1facv.scm ;;
;; ;;
;; Then loaded them into a Scheme-interpreter as: ;;
;; (load "GF2Xfacv.scm") ;;
;; (load "Xn_1facv.scm") ;;
;; and dumped out in binary format as: ;;
;; (fasdump GF2X_FACVEC "GF2Xffff.vec") ;;
;; (fasdump Xn_1_FACVEC "Xn_1_511.vec") ;;
;; so that they can be quickly loaded to this program with fasload. ;;
;; ;;
;; Copies of GF2Xfacv.scm and Xn_1facv.scm can be found at: ;;
;; http://www.iki.fi/~kartturi/matikka/Schemuli/GF2Xfacv.scm.gz ;;
;; and: ;;
;; http://www.iki.fi/~kartturi/matikka/Schemuli/Xn_1facv.scm.gz ;;
;; ;;
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;; /*
;; * Get Victor Shoup's NTL-library (version 5.3.1) from http://shoup.net/ntl/
;; *
;; * And after installing the library, compile this program as
;; * g++ -I/usr/local/include -L/usr/local/lib GF2Xfacs.c -o GF2Xfacs -lntl -lm
;; *
;; * where g++ --version gives:
;; * g++ (GCC) 3.2.2
;; * Copyright (C) 2002 Free Software Foundation, Inc.
;; *
;; * for the compiler what I have used now in January 2004.
;; *
;; */
;;
;; #include
;;
;; NTL_CLIENT
;;
;;
;; typedef unsigned long int ULLI;
;;
;; /*
;; n = 1: x + 1 11
;; n = 2: x² + 1 101
;; n = 3: x³ + 1 1001
;; n = 4: x^4 + 1 10001
;; n = 5: x^5 + 1 100001
;; n = 6: x^6 + 1 1000001
;; n = 7: x^7 + 1 10000001 (1 byte)
;; n = 8: x^8 + 1 100000001 (2 bytes)
;; n = 9: x^9 + 1 1000000001 (2 bytes)
;; n = 10: x^10 + 1 10000000001 (2 bytes)
;;
;; n = 15: x^15 + 1 1000000000000001 (2 bytes)
;; n = 16: x^16 + 1 10000000000000001 (3 bytes)
;;
;; Note: we should have: (list 3 3 137438953471 137438953471)
;; instead of (3 3 4294967295 4294967295)
;; for (Xn_1factor 74)
;; I.e. use bignums, not the integers!
;; */
;;
;;
;; void initXn_1(GF2X *p_z2p,ULLI n) /* n >= 1 */
;; {
;; int i;
;; unsigned char bytes[65];
;;
;; /* n divided by eight tells the number of intermediate zero-bytes needed. */
;; for(i=0; i < (n >> 3);)
;; {
;; bytes[i++] = 0;
;; }
;;
;; bytes[i] = 0;
;;
;; /* i now (n >> 3) */
;; bytes[0] = 1; /* The constant coefficient 1. */
;;
;; /* Then the leading coefficient: */
;; bytes[i++] |= (1 << (n & 7)); /* I.e. shift 1 to position (n mod 8). */
;;
;; /* i now (n >> 3)+1, the total number of bytes. */
;;
;; *p_z2p = GF2XFromBytes(bytes,(long)i);
;;
;; p_z2p->normalize(); /* Not necessary here?. */
;; }
;;
;;
;; void initFromBinexp(GF2X *p_z2p,ULLI n)
;; {
;; int i = 0;
;; unsigned char bytes[65];
;;
;; while(0 != n)
;; {
;; bytes[i] = (n&255);
;; i++;
;; n >>= 8;
;; }
;;
;; *p_z2p = GF2XFromBytes(bytes,(long)i);
;;
;; /* p_z2p->normalize(); Not necessary here. */
;;
;; }
;;
;; ULLI GF2XtoBinexp(GF2X p_z2p)
;; {
;; ULLI n = 0;
;; int i;
;;
;; unsigned char bytes[65];
;; long int n_bytes = NumBytes(p_z2p);
;;
;; BytesFromGF2X(bytes,p_z2p,n_bytes);
;;
;; for(i=n_bytes; i > 0; )
;; {
;; n <<= 8;
;; n |= bytes[--i];
;; }
;;
;; return(n);
;; }
;;
;;
;; ZZ GF2XtoZZ(GF2X p_z2p)
;; {
;; ULLI n = 0;
;; int i;
;;
;; unsigned char bytes[65];
;; long int n_bytes = NumBytes(p_z2p);
;;
;; BytesFromGF2X(bytes,p_z2p,n_bytes);
;; return(ZZFromBytes(bytes,n_bytes));
;; }
;;
;;
;; int main(int argc, char **argv)
;; {
;; int i,upto_n;
;; GF2X z2p;
;; vec_pair_GF2X_long factors;
;; const char *vec_name = "GF2X_FACVEC";
;; int compute_Xn_1_factorizations = 0;
;;
;; if(argc <= 1) { cerr << "Usage: GF2Xfacs upto_n\n"; exit(1); }
;; else { upto_n = atol(argv[1]); }
;;
;; if(upto_n < 0)
;; {
;; vec_name = "Xn_1_FACVEC";
;; upto_n = -upto_n;
;; compute_Xn_1_factorizations = 1;
;; }
;;
;; cout << "(define "; cout << vec_name; cout << " (make-vector ";
;; cout << (upto_n+1); cout << "))\n\n";
;;
;; for(i=1; i <= upto_n; i++)
;; {
;; int j,u;
;; if(compute_Xn_1_factorizations) { initXn_1(&z2p,i); }
;; else { initFromBinexp(&z2p,i); }
;;
;; CanZass(factors, z2p);
;; cout << "(vector-set! "; cout << vec_name; cout << " ";
;; cout << i; cout << " (sort (list";
;; u=factors.length();
;; for(j=0; j