/************************************************************************ Program: Autocorrelation-range EIS entry: %N A005434 Correlations of length n. This program computes the kappa sequence of [Guibas, Odlyzko 1981] here called s(n), that is the range of the autocorrelation function for words of lenght n. Binary words give the same range as larger alphabets [Guibas, Odlyzko 1981, Thm 5.1]. A lower bound (a partial count) for s(n) is the sequence g(n) which has a simple recurrence. g(n) = Sum_{0<=k0 and g(0) = 1. An upper bound is given by the sequence h(n) h(n) = 2 Sum_{0<=k<2n/3} h(k) for n>0 and h(0) = 1. Achim Flammenkamp thinks G(n) is an upper bound. G(n) = 2 Sum_{0<=k0 and G(0) = 1. Theorem: [Guibas, Odlyzko 1981, Thm 6.1] g(n) <= s(n) <= h(n) this means 1/(2*ln(2)) * ln(n)^2 + O(ln(n)) <= ln(s(n)) <= 1/(2*ln(1.5)) * ln(n)^2 + O(ln(n)) 1/(2*ln(2)) = 0.72134752 1/(2*ln(1.5)) = 1.23315173 Conjecture: [Flammenkamp 1984] g(n) <= s(n) <= G(n) this means ln(s(n)) = 1/(2*ln(2)) * ln(n)^2 + O(ln(n)) Table: n 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 s(n) 1 2 3 4 6 8 10 13 17 21 27 30 37 47 57 62 75 87 102 116 135 155 180 194 220 g(n) 1 1 3 3 5 5 7 7 10 10 13 13 18 18 23 23 30 30 37 37 47 47 57 57 70 G(n) 2 2 6 61010 22 22 34 34 54 54 74 74118118162162 230 230 298 298 406 406 514 Let c(k) = ln(s(k))/ln(k)^2 k SUM s(i) s(k) c(k) 2 i<=k 3 2 1.442695 4 10 4 0.721348 8 47 13 0.593178 16 345 62 0.536881 32 4132 479 0.513823 64 81137 5651 0.499505 128 2581347 105413 0.491273 256 134363131 3140766 0.486519 512 11680244730 154546957 0.484522 1024 1735856893587 12851613139 0.484475 25 1609 220 0.520562 50 26585 2249 0.504331 100 712107 35200 0.493635 200 31043203 887146 0.487877 400 2242057514 36367661 0.484967 800 274557525473 2502703116 0.484303 125 2581347 95457 0.491855 250 116394821 2778997 0.486694 500 9938264716 134123964 0.484558 1000 1449582463459 10949207362 0.484450 96 579093 29604 0.494193 192 24515676 723768 0.488119 384 1717635518 28836089 0.485091 768 203765388274 1922204117 0.484295 I computed s(n) for n=1..1025. For these values the relations c(k) >= c(2k) c(k) >= c(2k+1) are valid. But this is far off the range of Guibas and Odlyzko. !!! This is a effect of small numbers!!! The sequence g(n)=g_1/2(n) as a lower bound of s(n). For small values it seems that g(n)/s(n) will get 0 but actually we conjecture it will get 1 in the limit. Let c(k) = ln(g(k))/ln(k)^2 k g(k) c(k) 1 1 -- 2 1 0 4 2 0.360674 8 5 0.372204 16 18 0.375996 32 101 0.384231 64 914 0.394178 128 13669 0.404503 256 346002 0.414784 512 15125861 0.424803 1024 1160259474 0.434421 2048 158179790181 0.443572 4096 38738590246802 0.452233 8192 17197434971491685 0.460408 16384 13946948553384470418 0.468115 32768 20801852501722154798437 0.475378 65536 57394092679599617426401170 0.482227 131072 294440200461527865557589036389 0.488689 262144 2821322906713566368577851632986002 0.494791 524288 50696230714615530782170397980860222821 0.500560 1048576 1714436281238833563429247726066516726196114 0.506021 2097152 109468016758840716037232125004455181509123771749 0.511195 4194304 13235341870130346943270413920397922419167756292269970 0.516105 8388608 3038154089380384403189378033688960310709428246395156303205 0.520770 Let c(k) = ln(G(k))/ln(k)^2 k G(k) c(k) 1 2 -- 2 2 1.442700 4 6 0.932328 8 22 0.714844 16 118 0.620597 32 1046 0.578848 64 15702 0.558590 128 399190 0.547833 256 17449814 0.542289 512 1336408406 0.539955 1024 181971731798 0.539639 2048 44543346365782 0.540597 4096 19775048447292758 0.542358 8192 16041676322957890902 0.544626 16384 23933078568108290692438 0.547204 32768 66046901446088494993855830 0.549966 65536 338861259594750332197920265558 0.552826 131072 3246951705295431411825013405865302 0.555726 262144 58340594755827510290776270175897736534 0.558625 524288 1972776438659273563037657824675546034165078 0.561497 1048576 125952271100667647110015343508146950147805631830 0.564323 2097152 15227345601001005831201353121509502093685898136081750 0.567090 4194304 3495266605472441219429226674304715303240299252189429585238 0.569791 8388608 1526923948378492639896463764987834122332457857439516072961463638 0.572420 Approximation of g(q,s,n): The sum g(q,s,n) = s Sum_{0<=k #define M 1030 #define Unsigned int Unsigned d[M], j[M]; double count[M]; #if 0 #define Put if(n<10){int i; for(i=1;i<=h;i++) putchar(d[i]+'0'); putchar('\n');} /* the d[i] is the distance between two bits. */ /* Constructed(a): a = 0; for (i=1;i<=h;i++) a = (2*a+1)<<(d[i]-1); */ #else #define Put #endif void number_of_different (Unsigned max) { Unsigned h, n, k; #define divisible ( d[k+1] == 1 || !( d[k]%d[k+1] ) ) for (k=max; k>=0; k--) count[k]=0; n = 0; h = 0; j[0] = 0; for (;;) { h++; d[h] = 1; j[h] = ++n; count[n] += 1; Put; while (n2) { k= h-2; do { if (j[k] == n && divisible) goto valid; } while (--k > 0); } j[h] += 2; d[h] += 1; n++; for (k=h-1; k>0; k--) if (j[k] == n-2) goto valid; count[n] += 1; Put; } valid: do { while (j[h] == n--) if (--h == 0) return; j[h] -= 2; d[h] -= 1; } while (j[h-1] == n && d[h] == 1); } } #undef divisible int main (int argc, char ** argv) { Unsigned max, k; double total = 0; if (argc>1) { if (1 != sscanf(argv[1],"%u",&max)) return fprintf(stderr,"illegal parameter: no number %s\n", argv[1]), 2; } else { printf("Autocorrelation range for binary words.\nHow many letters? "); scanf("%u", &max); } if (max > M-1) return fprintf(stderr,"words too long. At most %u letters.\n", M-1), 1; number_of_different (max); for (k=1; k<=max; k++) { printf("%5d %12.0lf\n", k, count[k]); total += count[k]; } printf("Total %.0lf\n", total); return 0; }