Haskell中的素因子分解

Question

「綠色」整數可以被偶數除以2。
換句話說，數字的素因子分解有偶數個2。

例子：

•80是綠色的，因爲它可以通過2正好四次分，四是偶數。
（80 = 2 * 2 * 2 * 2 * 5，和5是未整除2）

•56不是綠色，因爲它可以由2個恰好三次進行劃分，和三個是奇數
（56 = 2 * 2 * 2 * 7和7是不是能被2整除）

•15是綠色的，因爲它可以通過2次零分，零甚至

我花了很這很多時間和解決方案是令人驚訝的簡潔：

green 0 = error "zero" 
green x 
    | mod x 2 == 0 = not (green (div x 2)) 
    | mod x 2 == 1 = True 

我無法確定「not（green（div x 2））」部分的用途。

Answer 1

這樣的事情？

green x = go x 0 
     where go 0 n = even n 
      go x n | mod x 2 == 0 = go (div x 2) (n+1) 
        | otherwise = even n 


> zip [1..] $ map green [1..16] 

[(1,True),(2,False),(3,True),(4,True),(5,True),(6,False),(7,True),(8,False),(9,True), 
(10,False),(11,True),(12,True),(13,True),(14,False),(15,True),(16,True)] 

Answer 2

如果x是2 n倍整除然後mod x 2由2 N-1次，什麼是我們試圖找出是當n爲偶數整除。 如果x是一個綠色數字，那麼mod x 2不是因爲如果n是偶數那麼n-1是奇數。 如果x不是綠色數字，那麼mod x 2是一個綠色數字，因爲如果n是奇數，那麼n-1是偶數。 這種遞推關係就足夠了，你不需要知道n，你只需要知道n是否是偶數，所以這個「不」就是n或n之間的切換。