Skip to content
This repository

HTTPS clone URL

Subversion checkout URL

You can clone with HTTPS or Subversion.

Download ZIP
branch: master
Fetching contributors…

Octocat-spinner-32-eaf2f5

Cannot retrieve contributors at this time

file 28 lines (19 sloc) 0.698 kb
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
module Math.BitSquares where

import Data.List
import qualified Data.Map as M
import Data.Maybe

squares a b = max 0 (squaresLTE b - squaresLTE (a-1))

squaresLTE x = sum [ k | (n,k) <- popCounts x, isSquare n ]

popCounts = M.toList . popCountsMap

popCountsMap n
    | n < 0 = M.empty
    | otherwise = M.unionWith (+) (popCountsLg2 l) (M.mapKeysMonotonic (1+) (popCountsMap r))
    where (l,r) = lg2Rem n

popCountsLg2 n = M.fromList [(k, bico n k) | k <- [0..n]]

isSquare n = n `elem` takeWhile (<= n) (map (^2) [0..])

bico n 0 = 1
bico 0 k = 0
bico n k = bico (n-1) (k-1) * n `div` k

lg2Rem 0 = (0, -1)
lg2Rem n = (l, n-2^l)
    where l = fromJust (findIndex (>n) (iterate (2*) 1)) - 1
Something went wrong with that request. Please try again.