Odd Numbers with Parity

#!/usr/bin/python

table=[]
for n in range(0,256):
    p=False
    while n:
        p = not p
        n &= n-1
    table.append(p)

parity_odd = []

print "Odd numbers with Parity:"



for i in range(0,256):
    if (i%2) and (table[i]):
        parity_odd.append(i)
        print i,

Result:

Odd numbers with Parity:
1 7 11 13 19 21 25 31 35 37 41 47 49 55 59 61 67 69 73 79 81 87 91 93 97 103 107 109 115 117 121 127 131 133 137 143 145 151 155 157 161 167 171 173 179 181 185 191 193 199 203 205 211 213 217 223 227 229 233 239 241 247 251 253

Fastest Fibonacci Sequencer

This algorithm is based on Fast-doubling  as explained in Fast Fibonacci algorithms.

Given F(k) and F(k+1), we can calculate these equations:

F(2k) = F(k)[2F(k+1)−F(k)]
F(2k+1) = F(k+1)2+F(k)2.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117

#include <stdio.h> #include <stdlib.h> #include <sys/types.h> #ifdef DEBUG #define DBGMSG(x) printf x #else #define DBGMSG(x) #endif typedef unsigned long long num_type; void _fib(int n, num_type *fn, num_type *fn_1); num_type fibonacci(uint n, num_type *s) { int i; num_type fn=0, fn_1=1; if (!s) return 0; if (n < 2) { return 1; } for(i=1; i<n; i++) { _fib(i, &fn, &fn_1); DBGMSG(("i=%u, n=%u, fn=%llu, fn+1=%llu\n", i, n, fn, fn_1)); s[i] = fn; } return s[n]; } /* * This is base on matrix exponentiation algorithm: * where: * f(2k) = f(k)*{ 2*f(k+1) - f(k)} ---> c * f(2k+1) = f(k)^2 + f(k+1)^2 ---> s * * if we plugin k = n/2, we get f(n) and f(n+1) */ void _fib(int n, num_type *fn, num_type *fn_1) { num_type c,d; num_type a, b; DBGMSG( ("%s: Initially n=%u, fn=%llu, fn_1=%llu\n", __FUNCTION__, n, *fn, *fn_1) ); if (n==0) { *fn = 0; // fn *fn_1 = 1; // fn+1 return; } else { a = *fn; b = *fn_1; } _fib(n>>1, &a, &b); DBGMSG (("%s: local fn=%llu, fn_1=%llu\n", __FUNCTION__, a, b)); c = a * (2*b - a); d = b*b + a*a; DBGMSG( ("%s: c=%llu, d=%llu\n", __FUNCTION__, c, d) ); if (n % 2 == 0) { // n is even *fn = c; *fn_1 = d; } else { *fn = d; *fn_1 = c+d; } } int main(int argc, char *argv[]) { uint n; uint f; int i; num_type *result; char *sbuf; int status = 0; if (argc > 1) n = atoi(argv[1]); else { printf("Enter a number: "); sbuf = (char *)malloc(50); status = (getline(&sbuf, &n, stdin) > 0); if (status == 0) { n = atoi(sbuf); free(sbuf); } else { printf("Error in input\n"); return (1); } } if (n <= 0) { printf("What have yo done???\n"); return(0); } if (status == 0) { result = (num_type *)malloc(n*sizeof(unsigned long long)); f = fibonacci(n, result); printf("Fibonacci sequence: "); for(i=0; i<n; i++) printf("%llu ", result[i]); printf("\n"); if (result) free(result); } }