/* http://oeis.org/A235921/a235921.txt A small C-program for computing the terms of A053669, A236454 and A235921 empirically, coded by Antti Karttunen, January 26 2014, and placed in Public Domain. Save and rename this C-source file as a235921.c and then compile it as gcc -o a235921 a235921.c Start for example as: ./a235921 100000 5 Start as: ./a235921 1 if you want to see all terms of A235921. The first such n that A053669(n) != A007978(n*n) but where n is not an odd multiple of 210 should occur at: 446185740 = 2*2*3*5*7*11*13*17*19*23 = 2124694 * 210 = 2*223092870 = 2*A002110(9) = 2*A034386(23). The second and third such differences should occur at 2*446185740 and 4*446185740 respectively. */ #include "stdio.h" #include "stdlib.h" #include "time.h" typedef unsigned long long int u64; #define tou64(x) ((u64)(x)) #define pow2(i) (tou64(1) << (i)) u64 gcd(u64 a,u64 b) { u64 ex_b; while(0 != b) { ex_b = b; b = a % b; a = ex_b; } return(a); } u64 A000142(u64 n) // Factorials, not needed in this program. { u64 z = 1; while(0 != n) { z *= n; n--; } return(z); } /* (define (A007978 n) (let loop ((m 1)) (if (not (zero? (modulo n m))) m (loop (+ 1 m))))) */ u64 A007978(u64 n) // Least non-divisor of n. { u64 m = 2; while(0 == (n%m)) { m++; } return(m); } /* (define (A053669 n) ;; Smallest k >= 2 coprime to n. (We don't need A000040 for this version). (let loop ((k 2)) (cond ((= 1 (gcd n k)) k) (else (loop (+ 1 k))) ) ) ) ;; Smallest prime not dividing n. (define (A053669v2 n) (let loop ((i 1)) (cond ((zero? (modulo n (A000040 i))) (loop (+ i 1))) (else (A000040 i))))) */ u64 A053669(u64 n) // Smallest k >= 2 coprime to n. = Smallest prime not dividing n. { u64 m = 2; while(1 != gcd(n,m)) { m++; } return(m); } /* (define A235921 (MATCHING-POS 1 1 (lambda (n) (not (= (A236454 n) (A053669 n)))))) (define (A236454 n) (A007978 (A000290 n))) */ u64 find_the_next_differing_one(u64 n) { n++; while(A053669(n) == A007978(n*n)) { n++; } return(n); } u64 compute_A235921_up_to_nth_different_from_A236432(int upto_nth_metadiff, u64 print_status_at_every_nth_one) { u64 n = 1; u64 odds = 1; u64 n2 = 210; u64 time_to_print = print_status_at_every_nth_one; u64 metadiffs = 0; while(1) { n = find_the_next_differing_one(n); if(n != n2) // An extra occurrence, n < n2 { metadiffs++; printf("The %Lu:th difference between A235921 and A236432: %Lu = %Lu*210 does not occur in the latter.\n", metadiffs, n, (n/210)); printf("n=%Lu, A053669(%Lu)=%Lu, A007978(%Lu)=%Lu\n", n, n, A053669(n), (n*n), A007978(n*n)); if(!--upto_nth_metadiff) { return(n); } } else // We are in sync with odd multiples of 210. { odds += 2; n2 = odds * 210; } if(!--time_to_print) { time_to_print = print_status_at_every_nth_one; printf("n=%Lu, A053669(%Lu)=%Lu, A236454(%Lu)=%Lu\n", n, n, A053669(n), n, A007978(n*n)); } } } int main(int argc, char **argv) { if(argc < 2) { fprintf(stderr,"Usage: %s print_status_at_every_nth_one [up_to_nth_metadifference]\n", *argv); exit(1); } else { u64 print_status_at_every_nth_one = tou64(atol(*(argv+1))); u64 up_to_nth_metadiff = ((argc < 3) ? 1 : tou64(atol(*(argv+2)))); u64 x = compute_A235921_up_to_nth_different_from_A236432(up_to_nth_metadiff, print_status_at_every_nth_one); printf("%Lu\n", x); } }