## Monday, October 01, 2012

### [ysihhflu] Iterated Fibonacci index

Let f be the inverse, or index, of the Fibonacci sequence shifted by two. f behaves approximately like a logarithm function (see Binet's formula).

 n f(n) 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 ... 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 ...

Consider the product n * f(n) * f(f(n)) * ..., terminating the product when a factor reaches 1. For input values which aren't exactly Fibonacci, we either take the floor or the ceiling.

Floor yields the sequence 1 1 2 6 8 30 36 42 64 72 80 88 96 390 420 450 480 510 540 570 600 756 792 828 864 900 936 972 1008 1044 1080 1116 1152 1188 1428 1470 1512 1554 1596 1638 1680 1722 1764 1806 1848 1890 1932 1974 2016 2058 2100 2142 2184 2226 2268 3520 3584 3648 3712 3776 3840 3904 3968 4032 4096 4160 4224 4288 4352 4416 4480 4544 4608 4672 4736 4800 4864 4928 4992 5056 5120 5184 5248 5312 5376 5440 5504 5568 5632 6408 6480 6552 6624 6696 6768 6840 6912 6984 7056 7128 7200.

Ceiling yields the sequence 1 1 2 6 24 30 144 168 192 270 300 330 360 390 2016 2160 2304 2448 2592 2736 2880 3024 3696 3864 4032 4200 4368 4536 4704 4872 5040 5208 5376 5544 5712 6720 6912 7104 7296 7488 7680 7872 8064 8256 8448 8640 8832 9024 9216 9408 9600 9792 9984 10176 10368 10560 15120 15390 15660 15930 16200 16470 16740 17010 17280 17550 17820 18090 18360 18630 18900 19170 19440 19710 19980 20250 20520 20790 21060 21330 21600 21870 22140 22410 22680 22950 23220 23490 23760 24030 27000 27300 27600 27900 28200 28500 28800 29100 29400 29700 30000.

The sum of reciprocals of these sequences diverge, but do so extremely slowly, perhaps slower than any integer sequence.

Previously, sequences formed from products of iterated log2.

module Main where { import Control.Exception(assert); {- |Fibonacci sequence shifted over by 2 so the value is always larger than the index. -} fibonacci :: [Integer]; fibonacci = 1 : 2 : zipWith (+) fibonacci (tail fibonacci); find_larger_fibonacci :: Int -> Integer -> Integer; find_larger_fibonacci current target = assert (0 < target) \$ if fibonacci !! current < target then find_larger_fibonacci (1 + current) target else fromIntegral current; floor_fibindex :: Integer -> Integer; floor_fibindex x = let { estimate :: Integer; estimate = find_larger_fibonacci 0 x } in if x == fibonacci !! fromInteger estimate then estimate else pred estimate; ceil_fibindex :: Integer -> Integer; ceil_fibindex x = find_larger_fibonacci 0 x; product_iterate :: (Integer -> Integer) -> Integer -> Integer; product_iterate f n = product \$ takeWhile (0<) \$ iterate f \$ n; main :: IO (); main = do { let { go :: (Integer -> Integer) -> IO (); go f = putStrLn \$ unwords \$ map (show . product_iterate f) \$ enumFromTo 0 100 }; go floor_fibindex; putStrLn ""; go ceil_fibindex; } }