Hello! This get from “250 problems in elementary number theory, (Modern analytic and computational methods in science and mathematics)” But have one question: How repair this code for complete work. (may be lazyness trick?)
isInteger :: RealFrac a => a -> Bool
isInteger x = fromIntegral (truncate x) == x
prf :: Int -> [Bool]
prf n = take n [x | j <- [0..], let x = isInteger ((j * j + 1) / (j + 1)), x == True ]
main = do
putStrLn "Search Integer result from sequences:"
print (prf 1000)
This code “works”, in the sense that it compiles and runs. It’s just working very hard!
Compiling with profiling:
ghc Main.hs -prof -fprof-auto
./Main +RTS -p
I get
Wed Mar 15 08:07 2023 Time and Allocation Profiling Report (Final)
Main +RTS -p -RTS
total time = 33.85 secs (33853 ticks @ 1000 us, 1 processor)
total alloc = 66,183,779,816 bytes (excludes profiling overheads)
COST CENTRE MODULE SRC %time %alloc
isInteger Main Main.hs:2:1-44 62.8 54.7
prf.x Main Main.hs:5:37-73 31.8 36.0
prf Main Main.hs:5:1-78 5.4 9.3
individual inherited
COST CENTRE MODULE SRC no. entries %time %alloc %time %alloc
MAIN MAIN <built-in> 128 0 0.0 0.0 100.0 100.0
CAF Main <entire-module> 255 0 0.0 0.0 100.0 100.0
main Main Main.hs:(7,1)-(9,19) 256 1 0.0 0.0 100.0 100.0
prf Main Main.hs:5:1-78 258 1 5.4 9.3 100.0 100.0
prf.x Main Main.hs:5:37-73 259 85145795 31.8 36.0 94.6 90.7
isInteger Main Main.hs:2:1-44 260 85145795 62.8 54.7 62.8 54.7
CAF GHC.Conc.Signal <entire-module> 250 0 0.0 0.0 0.0 0.0
CAF GHC.IO.Encoding <entire-module> 237 0 0.0 0.0 0.0 0.0
CAF GHC.IO.Encoding.Iconv <entire-module> 235 0 0.0 0.0 0.0 0.0
CAF GHC.IO.Exception <entire-module> 229 0 0.0 0.0 0.0 0.0
CAF GHC.IO.Handle.FD <entire-module> 227 0 0.0 0.0 0.0 0.0
CAF GHC.TopHandler <entire-module> 205 0 0.0 0.0 0.0 0.0
main Main Main.hs:(7,1)-(9,19) 257 0 0.0 0.0 0.0 0.0
Note that it tooks ~30 s for my computer to go through j = 0, 1, …, 85 145 795. I stopped the program manually after that.
Do you have a sense of what values of j might satisfy isInteger ((j * j + 1) / (j + 1))? Could it be that there’s some math trick which would allow you to skip over some values of j?
Another thing I would think about would be to stay far away from using floating-point values and floating-point operations for anything exact. I think the code is trying to select cases where j*j+1 is divisible by j+1, but your isInteger function is going to return true if (j*j+1) / (j+1) is too close to 1 to be distinguishable from 1. I’d go with something exact such as using Integer and testing rem x y == 0 instead.
This is a shot in the dark, since you didn’t actually describe what’s wrong …
Here’s a program that might do what you want, but it runs forever because it can only find two elements in the resulting list and you are asking for 1000:
import Data.Ratio ((%), denominator)
import System.IO (hSetBuffering, stdout, BufferMode(NoBuffering))
isInteger :: Rational -> Bool
isInteger x = denominator x == 1
prf :: Int -> [Integer]
prf n = take n [j | j <- [0..], isInteger ((j * j + 1) % (j + 1)) ]
main :: IO ()
main = do
putStrLn "Search Integer result from sequences:"
hSetBuffering stdout NoBuffering
print (prf 1000)
Depends on what you mean by the right result. To prove that only 0 and 1 should be in the result you would have to check all numbers. That is impossible! If you just want to check up to some bound like 1000 then you can do it like this:
import Data.Ratio ((%), denominator)
isInteger :: Rational -> Bool
isInteger x = denominator x == 1
prf :: Int -> [Integer]
prf n = [j | j <- [0..n], isInteger ((j * j + 1) % (j + 1)) ]
main :: IO ()
main = do
putStrLn "Search Integer result from sequences:"
print (prf 1000)