genericLength

Huecos de Euclides

PorJosé A. Alonso 29-noviembre-20166-diciembre-2016

El teorema de Euclides afirma que existen infinitos números primos. En palabras de Euclides,

«Hay más números primos que cualquier cantidad propuesta de números primos.» (Proposición 20 del Libro IX de «Los Elementos»)

Su demostración se basa en que si p₁,…,pₙ son los primeros n números primos, entonces entre 1+pₙ y 1+p₁·p₂·…·pₙ hay algún número primo. La cantidad de dichos números primos se llama el n-ésimo hueco de Euclides. Por ejemplo, para n = 3 se tiene que p₁ = 2, p₂ = 3 y p₃ = 5 entre 1+p₃ = 6 y 1+p₁·p₂·p₃ = 31 hay 8 números primos (7, 11, 13, 17, 19, 23, 29 y 31), por lo que el valor del tercer hueco de Euclides es 8.

Definir la función

   hueco :: Int -> Integer

1	hueco :: Int -> Integer

tal que (hueco n) es el n-ésimo hueco de Eulides. Por ejemplo,

   hueco 3                   ==  8
   [hueco n | n <- [1..8]]   ==  [1,2,8,43,339,3242,42324,646021]

1 2	hueco 3 == 8 [hueco n \| n <- [1..8]] == [1,2,8,43,339,3242,42324,646021]

Soluciones

import Data.List
import Data.Numbers.Primes

hueco :: Int -> Integer
hueco n = nPrimosEntre (primes !! (n-1)) (1 + product (take n primes))

-- (nPrimosEntre x y) es el número de primos entre x e y. Por ejemplo, 
--    nPrimosEntre 3 7  ==  2
nPrimosEntre :: Integer -> Integer -> Integer
nPrimosEntre x y = genericLength (primosEntre x y)

-- (primosEntre x y) es la lista de los números de primos entre x e
-- y. Por ejemplo,  
--    primosEntre 3 7  ==  [5,7]
primosEntre :: Integer -> Integer -> [Integer]
primosEntre x y =
  takeWhile (<=y) (dropWhile (<=x) primes)

import Data.List

import Data.Numbers.Primes

hueco :: Int -> Integer

hueco n = nPrimosEntre (primes !! (n-1)) (1 + product (take n primes))

-- (nPrimosEntre x y) es el número de primos entre x e y. Por ejemplo,

-- nPrimosEntre 3 7 == 2

nPrimosEntre :: Integer -> Integer -> Integer

nPrimosEntre x y = genericLength (primosEntre x y)

-- (primosEntre x y) es la lista de los números de primos entre x e

-- y. Por ejemplo,

-- primosEntre 3 7 == [5,7]

primosEntre :: Integer -> Integer -> [Integer]

primosEntre x y =

takeWhile (<=y) (dropWhile (<=x) primes)

Referencias

Euclid’s theorem en la ProofWiki.

Caminos en una retícula

PorJosé A. Alonso 26-mayo-20162-junio-2016

El problema de los caminos en una retícula consiste en, dada una retícula rectangular con m filas y n columnas, determinar todos los caminos para ir desde el vértice inferior izquierdo hasta el vértice superior derecho donde los movimientos permitidos son mover hacia el siguiente vértice a la derecha o arriba.

Por ejemplo, en la siguiente retícula un posible camino es el indicado en rojo.

Para representar los caminos se definen los siguientes tipos de datos:

    data Direccion = D | A deriving (Show, Eq)
    type Camino = [Direccion]

1 2	data Direccion = D \| A deriving (Show, Eq) type Camino = [Direccion]

Por tanto, el camino de la figura anterior se representa por la lista [D,D,A,D,A].

Definir las funciones

   caminos  :: Int -> Int -> [Camino]
   nCaminos :: Int -> Int -> Integer

1 2	caminos :: Int -> Int -> [Camino] nCaminos :: Int -> Int -> Integer

tales que

(caminos m n) es la lista de los caminos en una retícula rectangular con m filas y n columnas. Por ejemplo,

     λ> caminos 2 2
     [[A,A,D,D],[A,D,A,D],[A,D,D,A],[D,A,A,D],[D,A,D,A],[D,D,A,A]]
     λ> caminos 1 3
     [[A,A,A,D],[A,A,D,A],[A,D,A,A],[D,A,A,A]]
     λ> caminos 2 3
     [[A,A,A,D,D],[A,A,D,A,D],[A,A,D,D,A],[A,D,A,A,D],[A,D,A,D,A],[A,D,D,A,A],
      [D,A,A,A,D],[D,A,A,D,A],[D,A,D,A,A],[D,D,A,A,A]]

λ> caminos 2 2

[[A,A,D,D],[A,D,A,D],[A,D,D,A],[D,A,A,D],[D,A,D,A],[D,D,A,A]]

λ> caminos 1 3

[[A,A,A,D],[A,A,D,A],[A,D,A,A],[D,A,A,A]]

λ> caminos 2 3

[[A,A,A,D,D],[A,A,D,A,D],[A,A,D,D,A],[A,D,A,A,D],[A,D,A,D,A],[A,D,D,A,A],

[D,A,A,A,D],[D,A,A,D,A],[D,A,D,A,A],[D,D,A,A,A]]

(nCaminos m n) es el número de los caminos en una retícula rectangular con m filas y n columnas. Por ejemplo,

     nCaminos 2 2  ==  6
     nCaminos 1 3  ==  4
     nCaminos 2 3  ==  10
     length (show (nCaminos 20000 30000))  ==  14612
     length (show (nCaminos 30000 20000))  ==  14612

nCaminos 2 2 == 6

nCaminos 1 3 == 4

nCaminos 2 3 == 10

length (show (nCaminos 20000 30000)) == 14612

length (show (nCaminos 30000 20000)) == 14612

Soluciones

import Data.List (genericLength)

data Direccion = D | A deriving (Show, Eq)

type Camino = [Direccion]

-- Definición de caminos
-- =====================

caminos :: Int -> Int -> [Camino]
caminos 0 n = [replicate n A]
caminos m 0 = [replicate m D]
caminos m n = [A:xs | xs <- caminos m (n-1)] ++
              [D:xs | xs <- caminos (m-1) n]

-- 1ª definición de nCaminos
-- =========================

nCaminos1 :: Int -> Int -> Integer
nCaminos1 m n = genericLength (caminos m n)

-- 2ª definición de nCaminos
-- =========================

nCaminos2 :: Int -> Int -> Integer
nCaminos2 0 n = 1
nCaminos2 m 0 = 1
nCaminos2 m n = nCaminos2 m (n-1) + nCaminos2 (m-1) n

-- 3ª definición de nCaminos
-- =========================

-- Los caminos desde (0,0) a (m,n) son las permutaciones con repetición
-- de m veces la D y n veces la A. Por tanto, su número es
--    (m+n)! / m!*n!

nCaminos3 :: Int -> Int -> Integer
nCaminos3 m n = 
    fact (m+n) `div` (fact m * fact n)

fact :: Int -> Integer
fact n = product [1..fromIntegral n]

-- 4ª solución de nCaminos
-- =======================

nCaminos4 :: Int -> Int -> Integer
nCaminos4 m n = 
    product [a+1..a+b] `div` product [2..b]
    where m' = fromIntegral m
          n' = fromIntegral n
          a  = max m' n'
          b  = min m' n'

-- Comparación de eficiencia
-- =========================

--    λ> nCaminos1 10 10
--    184756
--    (3.50 secs, 656,909,648 bytes)
--    λ> nCaminos2 10 10
--    184756
--    (0.50 secs, 47,330,272 bytes)
--    λ> nCaminos3 10 10
--    184756
--    (0.01 secs, 0 bytes)
--    λ> nCaminos4 10 10
--    184756
--    (0.01 secs, 0 bytes)
-- 
--    λ> nCaminos2 10 15
--    3268760
--    (8.83 secs, 1,142,623,080 bytes)
--    λ> nCaminos3 10 15
--    3268760
--    (0.01 secs, 0 bytes)
--    λ> nCaminos4 10 15
--    3268760
--    (0.00 secs, 0 bytes)
--
--    λ> let n = 2*10^4 
--    (0.01 secs, 0 bytes)
--    λ> length (show (nCaminos3 n n))
--    12039
--    (8.41 secs, 2,369,767,480 bytes)
--    λ> length (show (nCaminos4 n n))
--    12039
--    (2.98 secs, 833,386,648 bytes)

import Data.List (genericLength)

data Direccion = D | A deriving (Show, Eq)

type Camino = [Direccion]

-- Definición de caminos

-- =====================

caminos :: Int -> Int -> [Camino]

caminos 0 n = [replicate n A]

caminos m 0 = [replicate m D]

caminos m n = [A:xs | xs <- caminos m (n-1)] ++

[D:xs | xs <- caminos (m-1) n]

-- 1ª definición de nCaminos

-- =========================

nCaminos1 :: Int -> Int -> Integer

nCaminos1 m n = genericLength (caminos m n)

-- 2ª definición de nCaminos

-- =========================

nCaminos2 :: Int -> Int -> Integer

nCaminos2 0 n = 1

nCaminos2 m 0 = 1

nCaminos2 m n = nCaminos2 m (n-1) + nCaminos2 (m-1) n

-- 3ª definición de nCaminos

-- =========================

-- Los caminos desde (0,0) a (m,n) son las permutaciones con repetición

-- de m veces la D y n veces la A. Por tanto, su número es

-- (m+n)! / m!*n!

nCaminos3 :: Int -> Int -> Integer

nCaminos3 m n =

fact (m+n) `div` (fact m * fact n)

fact :: Int -> Integer

fact n = product [1..fromIntegral n]

-- 4ª solución de nCaminos

-- =======================

nCaminos4 :: Int -> Int -> Integer

nCaminos4 m n =

product [a+1..a+b] `div` product [2..b]

where m' = fromIntegral m

n' = fromIntegral n

a = max m' n'

b = min m' n'

-- Comparación de eficiencia

-- =========================

-- λ> nCaminos1 10 10

-- 184756

-- (3.50 secs, 656,909,648 bytes)

-- λ> nCaminos2 10 10

-- 184756

-- (0.50 secs, 47,330,272 bytes)

-- λ> nCaminos3 10 10

-- 184756

-- (0.01 secs, 0 bytes)

-- λ> nCaminos4 10 10

-- 184756

-- (0.01 secs, 0 bytes)

-- λ> nCaminos2 10 15

-- 3268760

-- (8.83 secs, 1,142,623,080 bytes)

-- λ> nCaminos3 10 15

-- 3268760

-- (0.01 secs, 0 bytes)

-- λ> nCaminos4 10 15

-- 3268760

-- (0.00 secs, 0 bytes)

-- λ> let n = 2*10^4

-- (0.01 secs, 0 bytes)

-- λ> length (show (nCaminos3 n n))

-- 12039

-- (8.41 secs, 2,369,767,480 bytes)

-- λ> length (show (nCaminos4 n n))

-- 12039

-- (2.98 secs, 833,386,648 bytes)

Densidad de números no monótonos

PorJosé A. Alonso 11-mayo-201618-mayo-2016

Un número entero positivo se dice que es

creciente si cada uno de sus dígitos es menor o igual que el que está a su derecha; por ejemplo, 134479.
decreciente si cada uno de sus dígitos es menor o igual que el que está a su derecha; por ejemplo, 664210.
no monótono si no es creciente ni decreciente; por ejemplo, 155369.

Para cada entero positivo n, la densidad números no monótonos hasta n es el cociente entre la cantidad de n números no monótonos entre menores o iguales que n y el número n. Por ejemplo, hasta 150 hay 19 números no monótonos (101, 102, 103, 104, 105, 106, 107, 108, 109, 120, 121, 130, 131, 132, 140, 141, 142, 143 y 150); por tanto, la densidad hasta 150 es 19/150 = 0.12666667

Definir las siguientes funciones

   densidad              :: Integer -> Float
   menorConDensidadMayor :: Float -> Integer

1 2	densidad :: Integer -> Float menorConDensidadMayor :: Float -> Integer

tales que

(densidad n) es la densidad de números no monótonos hasta n. Por ejemplo,

     densidad 100  ==  0.0
     densidad 200  ==  0.265
     densidad 400  ==  0.4375
     densidad 800  ==  0.53375

densidad 100 == 0.0

densidad 200 == 0.265

densidad 400 == 0.4375

densidad 800 == 0.53375

(menorConDensidadMayor x) es el menor número n tal que la densidad de números no monótonos hasta n es mayor o igual que x. Por ejemplo,

     menorConDensidadMayor 0.5   ==  538
     densidad 537                ==  0.49906892
     densidad 538                ==  0.5
     menorConDensidadMayor 0.9   ==  21780
     densidad 21779              ==  0.8999954
     densidad 21780              ==  0.9
     menorConDensidadMayor 0.99  ==  1586996

menorConDensidadMayor 0.5 == 538

densidad 537 == 0.49906892

densidad 538 == 0.5

menorConDensidadMayor 0.9 == 21780

densidad 21779 == 0.8999954

densidad 21780 == 0.9

menorConDensidadMayor 0.99 == 1586996

Soluciones

import Data.List (genericLength, sort)

-- 1ª definición
-- =============

densidad :: Integer -> Float
densidad n = 
    genericLength [x | x <- [1..n], esNoMonotono x] / fromIntegral n

esNoMonotono :: Integer -> Bool
esNoMonotono x = not (esCreciente x) && not (esDecreciente x)

esCreciente :: Integer -> Bool
esCreciente x = show x == sort (show x)

esDecreciente :: Integer -> Bool
esDecreciente x = reverse (show x) == sort (show x)

menorConDensidadMayor :: Float -> Integer 
menorConDensidadMayor x  = 
    buscaProporcion x (filter esNoMonotono [1..])
    where buscaProporcion x = 
              snd . head . filter condicion . zip [1..]
              where condicion (a,b) = a >= x * fromIntegral b

import Data.List (genericLength, sort)

-- 1ª definición

-- =============

densidad :: Integer -> Float

densidad n =

genericLength [x | x <- [1..n], esNoMonotono x] / fromIntegral n

esNoMonotono :: Integer -> Bool

esNoMonotono x = not (esCreciente x) && not (esDecreciente x)

esCreciente :: Integer -> Bool

esCreciente x = show x == sort (show x)

esDecreciente :: Integer -> Bool

esDecreciente x = reverse (show x) == sort (show x)

menorConDensidadMayor :: Float -> Integer

menorConDensidadMayor x =

buscaProporcion x (filter esNoMonotono [1..])

where buscaProporcion x =

snd . head . filter condicion . zip [1..]

where condicion (a,b) = a >= x * fromIntegral b

Elemento ausente

PorJosé A. Alonso 8-marzo-20162-mayo-2016

Sea xs una lista y n su longitud. Se dice que xs es casi completa si sus elementos son los números enteros entre 0 y n excepto uno. Por ejemplo, la lista [3,0,1] es casi completa.

Definir la función

   ausente :: [Integer] -> Integer

1	ausente :: [Integer] -> Integer

tal que (ausente xs) es el único entero (entre 0 y la longitud de xs) que no pertenece a la lista casi completa xs. Por ejemplo,

   ausente [3,0,1]               ==  2
   ausente [1,2,0]               ==  3
   ausente (1+10^7:[0..10^7-1])  ==  10000000

ausente [3,0,1] == 2

ausente [1,2,0] == 3

ausente (1+10^7:[0..10^7-1]) == 10000000

Soluciones

import Data.List (foldl', genericLength)
import Data.Set (fromList, notMember)
    
-- 1ª definición
ausente1 :: [Integer] -> Integer
ausente1 xs =
    head [n | n <- [0..], n `notElem` xs]

-- 2ª definición
ausente2 :: [Integer] -> Integer
ausente2 xs =
    head [n | n <- [0..], n `notMember` ys]
    where ys = fromList xs
         
-- 3ª definición (lineal)
ausente3 :: [Integer] -> Integer
ausente3 xs =
    ((n * (n+1)) `div` 2) - sum xs
    where n = genericLength xs  

-- 4ª definición
ausente4 :: [Integer] -> Integer
ausente4 xs =
    ((n * (n+1)) `div` 2) - foldl' (+) 0 xs
    where n = genericLength xs  

-- Comparación de eficiencia
-- =========================

--    λ> let n = 10^5 in ausente1 (n+1:[0..n-1])
--    100000
--    (68.51 secs, 25,967,840 bytes)
--    λ> let n = 10^5 in ausente2 (n+1:[0..n-1])
--    100000
--    (0.12 secs, 123,488,144 bytes)
--    λ> let n = 10^5 in ausente3 (n+1:[0..n-1])
--    100000
--    (0.07 secs, 30,928,384 bytes)
--    λ> let n = 10^5 in ausente4 (n+1:[0..n-1])
--    100000
--    (0.02 secs, 23,039,904 bytes)
--    
--    λ> let n = 10^7 in ausente2 (n+1:[0..n-1])
--    10000000
--    (14.32 secs, 15,358,509,280 bytes)
--    λ> let n = 10^7 in ausente3 (n+1:[0..n-1])
--    10000000
--    (5.57 secs, 2,670,214,936 bytes)
--    λ> let n = 10^7 in ausente4 (n+1:[0..n-1])
--    10000000
--    (3.36 secs, 2,074,919,184 bytes)

import Data.List (foldl', genericLength)

import Data.Set (fromList, notMember)

-- 1ª definición

ausente1 :: [Integer] -> Integer

ausente1 xs =

head [n | n <- [0..], n `notElem` xs]

-- 2ª definición

ausente2 :: [Integer] -> Integer

ausente2 xs =

head [n | n <- [0..], n `notMember` ys]

where ys = fromList xs

-- 3ª definición (lineal)

ausente3 :: [Integer] -> Integer

ausente3 xs =

((n * (n+1)) `div` 2) - sum xs

where n = genericLength xs

-- 4ª definición

ausente4 :: [Integer] -> Integer

ausente4 xs =

((n * (n+1)) `div` 2) - foldl' (+) 0 xs

where n = genericLength xs

-- Comparación de eficiencia

-- =========================

-- λ> let n = 10^5 in ausente1 (n+1:[0..n-1])

-- 100000

-- (68.51 secs, 25,967,840 bytes)

-- λ> let n = 10^5 in ausente2 (n+1:[0..n-1])

-- 100000

-- (0.12 secs, 123,488,144 bytes)

-- λ> let n = 10^5 in ausente3 (n+1:[0..n-1])

-- 100000

-- (0.07 secs, 30,928,384 bytes)

-- λ> let n = 10^5 in ausente4 (n+1:[0..n-1])

-- 100000

-- (0.02 secs, 23,039,904 bytes)

-- λ> let n = 10^7 in ausente2 (n+1:[0..n-1])

-- 10000000

-- (14.32 secs, 15,358,509,280 bytes)

-- λ> let n = 10^7 in ausente3 (n+1:[0..n-1])

-- 10000000

-- (5.57 secs, 2,670,214,936 bytes)

-- λ> let n = 10^7 in ausente4 (n+1:[0..n-1])

-- 10000000

-- (3.36 secs, 2,074,919,184 bytes)

Particiones en sumas de cuadrados

PorJosé A. Alonso 26-febrero-20161-mayo-2016

Definir las funciones

   particionesCuadradas        :: Integer -> [[Integer]]
   nParticionesCuadradas       :: Integer -> Integer
   graficaParticionesCuadradas :: Integer -> IO ()

particionesCuadradas :: Integer -> [[Integer]]

nParticionesCuadradas :: Integer -> Integer

graficaParticionesCuadradas :: Integer -> IO ()

tales que

(particionesCuadradas n) es la listas de conjuntos de cuadrados cuya suma es n. Por ejemplo,

      particionesCuadradas 3  ==  [[1,1,1]]
      particionesCuadradas 4  ==  [[4],[1,1,1,1]]
      particionesCuadradas 9  ==  [[9],[4,4,1],[4,1,1,1,1,1],[1,1,1,1,1,1,1,1,1]]

particionesCuadradas 3 == [[1,1,1]]

particionesCuadradas 4 == [[4],[1,1,1,1]]

particionesCuadradas 9 == [[9],[4,4,1],[4,1,1,1,1,1],[1,1,1,1,1,1,1,1,1]]

(nParticionesCuadradas n) es el número de conjuntos de cuadrados cuya suma es n. Por ejemplo,

      nParticionesCuadradas 3    ==  1
      nParticionesCuadradas 4    ==  2
      nParticionesCuadradas 9    ==  4
      nParticionesCuadradas 50   ==  104
      nParticionesCuadradas 100  ==  1116
      nParticionesCuadradas 200  ==  27482

nParticionesCuadradas 3 == 1

nParticionesCuadradas 4 == 2

nParticionesCuadradas 9 == 4

nParticionesCuadradas 50 == 104

nParticionesCuadradas 100 == 1116

nParticionesCuadradas 200 == 27482

(graficaParticionesCuadradas n) dibuja la gráfica de la sucesión

      [nParticionesCuadradas k | k <- [0..n]]

1	[nParticionesCuadradas k \| k <- [0..n]]

Por ejemplo, con (graficaParticionesCuadradas 100) se obtiene

Soluciones

import Data.List (genericLength)
import Graphics.Gnuplot.Simple

-- Definición de particiones cuadradas
-- ===================================

particionesCuadradas :: Integer -> [[Integer]]
particionesCuadradas n = 
    particiones n (reverse $ takeWhile (<=n) cuadrados)

-- cuadrados es la lista de los cuadrados. Por ejemplo,
--    take 12 cuadrados  ==  [1,4,9,16,25,36,49,64,81,100,121,144]
cuadrados :: [Integer]
cuadrados = map (^2) [1..]

-- (particiones n xs) es la lista de las particiones de n como suma de
-- elementos de xs, donde xs es una lista no creciente. Por ejemplo,
--    particiones 10 [7,4,2]  ==  [[4,4,2],[4,2,2,2],[2,2,2,2,2]]
--    particiones 11 [7,4,2]  ==  [[7,4],[7,2,2]]
--    particiones  5 [7,4,2]  ==  []
particiones:: Integer -> [Integer] -> [[Integer]]
particiones _ [] = []
particiones n (x:xs)
    | x >  n    = particiones n xs
    | x == n    = [n] : particiones n xs
    | otherwise = map (x:) (particiones (n-x) (x:xs)) ++ particiones n xs

-- 1ª definición de nParticionesCuadradas       
nParticionesCuadradas1 :: Integer -> Integer
nParticionesCuadradas1 = genericLength . particionesCuadradas

-- 2ª definición nParticionesCuadradas   
nParticionesCuadradas2 :: Integer -> Integer
nParticionesCuadradas2 n = aux n (reverse $ takeWhile (<=n) cuadrados) where
    aux _ [] = 0
    aux n ys@(x:xs) | x >  n    = aux n xs
                    | x == n    = 1 + aux n xs
                    | otherwise = aux (n-x) ys + aux n xs

-- Comparación de eficiencia
-- =========================

--    λ> nParticionesCuadradas1 250
--    94987
--    (4.21 secs, 3,256,031,528 bytes)
--    λ> nParticionesCuadradas2 250
--    94987
--    (2.93 secs, 1,714,701,504 bytes)

-- Definición de graficaParticionesCuadradas
-- =========================================
                                  
graficaParticionesCuadradas :: Integer  -> IO ()
graficaParticionesCuadradas n = 
    plotList [Key Nothing] [nParticionesCuadradas2 k | k <- [0..n]]

import Data.List (genericLength)

import Graphics.Gnuplot.Simple

-- Definición de particiones cuadradas

-- ===================================

particionesCuadradas :: Integer -> [[Integer]]

particionesCuadradas n =

particiones n (reverse $ takeWhile (<=n) cuadrados)

-- cuadrados es la lista de los cuadrados. Por ejemplo,

-- take 12 cuadrados == [1,4,9,16,25,36,49,64,81,100,121,144]

cuadrados :: [Integer]

cuadrados = map (^2) [1..]

-- (particiones n xs) es la lista de las particiones de n como suma de

-- elementos de xs, donde xs es una lista no creciente. Por ejemplo,

-- particiones 10 [7,4,2] == [[4,4,2],[4,2,2,2],[2,2,2,2,2]]

-- particiones 11 [7,4,2] == [[7,4],[7,2,2]]

-- particiones 5 [7,4,2] == []

particiones:: Integer -> [Integer] -> [[Integer]]

particiones _ [] = []

particiones n (x:xs)

| x > n = particiones n xs

| x == n = [n] : particiones n xs

| otherwise = map (x:) (particiones (n-x) (x:xs)) ++ particiones n xs

-- 1ª definición de nParticionesCuadradas

nParticionesCuadradas1 :: Integer -> Integer

nParticionesCuadradas1 = genericLength . particionesCuadradas

-- 2ª definición nParticionesCuadradas

nParticionesCuadradas2 :: Integer -> Integer

nParticionesCuadradas2 n = aux n (reverse $ takeWhile (<=n) cuadrados) where

aux _ [] = 0

aux n ys@(x:xs) | x > n = aux n xs

| x == n = 1 + aux n xs

| otherwise = aux (n-x) ys + aux n xs

-- Comparación de eficiencia

-- =========================

-- λ> nParticionesCuadradas1 250

-- 94987

-- (4.21 secs, 3,256,031,528 bytes)

-- λ> nParticionesCuadradas2 250

-- 94987

-- (2.93 secs, 1,714,701,504 bytes)

-- Definición de graficaParticionesCuadradas

-- =========================================

graficaParticionesCuadradas :: Integer -> IO ()

graficaParticionesCuadradas n =

plotList [Key Nothing] [nParticionesCuadradas2 k | k <- [0..n]]

Referencias

Sucesión A001156 de OEIS.

Huecos de Euclides

Soluciones

Referencias

Caminos en una retícula

Soluciones

Densidad de números no monótonos

Soluciones

Elemento ausente

Soluciones

Particiones en sumas de cuadrados

Soluciones

Referencias

Entradas recientes

Buscar

Correo electrónico