Day 280

October 9, 2017

Since we already have code to deal with prime numbers, this is easy:

(define (sum-mod-prime-day limit)
  (let ((pgen (primegen)))
    (let loop ((sum (pgen)) (mod 1) (zs (list)))
      (if (< limit mod) (reverse zs)
        (if (prime? (modulo sum mod))
            (loop (+ sum (pgen)) (+ mod 1) (cons mod zs))
            (loop (+ sum (pgen)) (+ mod 1) zs))))))
> (sum-mod-prime-day 365)
(5 6 7 8 12 15 16 19 20 21 24 26 30 34 37 38 40 42 44 45 46
 48 49 50 55 58 59 60 62 64 65 66 67 68 70 72 73 75 76 78 86
 87 88 92 102 116 120 122 124 128 130 132 135 140 143 145 150
 156 158 164 165 166 168 172 173 175 176 182 183 191 196 210
 214 216 218 223 234 236 241 248 250 256 259 262 265 266 272
 280 285 301 306 310 311 314 315 324 328 330 336 337 344 347
 348 349 352 355 358 365)
> 108

You can run the program, and see the prime generator and primality tester, at https://ideone.com/TyDKiX.

First I thought there would not be many such days, because if there were, they would not be interesting. But then I realized that the sums mod n are small, and lots of small numbers are prime, so there should be lots of results, which is correct.

I’ve added Ballew’s blog to my blog rotation. You might want to do the same.

Advertisements

Pages: 1 2

7 Responses to “Day 280”

  1. Using the primes package for Haskell, the simple solution works just fine:

    module Main where
    
    import Data.Numbers.Primes (isPrime, primes)
    
    sumPrimesMod :: Int -> Bool
    sumPrimesMod n = isPrime (sum (take n primes) `mod` n)
    
    main :: IO ()
    main = do
      let ns = filter sumPrimesMod [1 .. 367]
      print ns
      print $ length ns
    

    I went up to 367 to include leap years.

  2. Perl ‘golf’ish solution – using a bit of bash and a bit of perl!

    perl -e '%p=map{$_,1}@ARGV;print"@{[grep{$p{($t+=shift)%$_}}1..366]}\n"' `seq 2 2473|factor|sed 's/.*: //g;/ /d'| xargs`
    

    The bash in back ticks generates a list of 365 primes…
    Get a list of 108 numbers – can add “|wc -w” to the end to get the number of values which satisfy this….

  3. mcmillhj said

    SML:

    fun isPrime n =
      if n = 2 then true
      else if n < 2 orelse n mod 2 = 0 then false
      else let
        fun loop k =
          if k * k > n then true
          else if n mod k = 0 then false
          else loop (k + 2)
        in loop 3
      end ;
    
    fun primesUpTo n = let
      fun loop n 0 acc = rev acc
        | loop n count acc = if isPrime n
                             then loop (n + 2) (count - 1) (n :: acc)
                             else loop (n + 2) count acc
    
    in
      loop 3 (n-1) [2]
    end ;
    
    val primes = primesUpTo 365;
    fun sumPrimesMod n = let
      val nPrimes = List.take(primes, n)
      val sum = foldl (op +) 0
    in
      isPrime (sum nPrimes mod n)
    end ;
    
    val matchingDays = List.filter (fn x => sumPrimesMod x) (List.tabulate(365, fn x => x + 1));
    (* [5, 6, 7, 8, 12, 15, 16, 19, 20, 21, 24, 26, 30, 34, 37, 38, 40, 42, 44, 45,
     46, 48, 49, 50, 55, 58, 59, 60, 62, 64, 65, 66, 67, 68, 70, 72, 73, 75, 76,
     78, 86, 87, 88, 92, 102, 116, 120, 122, 124, 128, 130, 132, 135, 140, 143,
     145, 150, 156, 158, 164, 165, 166, 168, 172, 173, 175, 176, 182, 183, 191,
     196, 210, 214, 216, 218, 223, 234, 236, 241, 248, 250, 256, 259, 262, 265,
     266, 272, 280, 285, 301, 306, 310, 311, 314, 315, 324, 328, 330, 336, 337,
     344, 347, 348, 349, 352, 355, 358, 365] *)
    
  4. Rutger said
    def is_prime(n):
    	return (n > 1) and (n == 2 or n % 2) and all(n % x for x in range(3, int(1 + n**0.5), 2))
    
    def first_n_primes(n):
    	result, i, x = [], 0, 2
    	while i < n:
    		if is_prime(x):
    			result.append(x)
    			i += 1
    		x += 1
    	return result
    
    first_365 = first_n_primes(365)
    
    for day in range(1,365):
    	if is_prime(sum(first_365[:day]) % day):
    		print(day)
    
    
  5. matthew said

    Here’s another Haskell solution, this one builds a list of the partial sums with scanl rather than recomputing each time around:

    import Data.Numbers.Primes (isPrime, primes)
    main = print $ 
         map snd $ 
         filter (isPrime . uncurry mod) $ 
         take 366 $
         zip (scanl1 (+) primes) [1..]
    
  6. chaw said

    Using standard (R7RS) Scheme and popular a couple of popular libraries
    (SRFI-1 and SLIB’s factor):

    (import (scheme base)
            (scheme write)
            (only (slib factor) primes>)
            (only (srfi 1) iota fold filter take-while))
    
    (display
     (let* ((n 366)
            (nprimes (primes> 1 n))
            (sum-nprimes (reverse (fold (lambda (p sums)
                                          (cons (+ p (car sums))
                                                sums))
                                        (list (car nprimes))
                                        (cdr nprimes))))
            (mprimes (take-while (lambda (v) (< v n)) nprimes)))
       (length (filter (lambda (pr)
                         (member (modulo (cdr pr) (car pr))
                                 mprimes))
                       (map cons (iota n 1) sum-nprimes)))))
    (newline)
    

  7. Steve said

    Klong 20170905

    prime::{:[x<2; 0; :[x=2; 1; &/x!:\2+!_x^1%2]]}
    
    nextPrime::{[a]; a::x+1; {x; prime(a)=0}{x; a::a+1}:~a; a}
    
    findPrimes::{[max numprimes primes sum]; max::x; numprimes::sum::0; primes::[]; {x; max>numprimes}{num::nextPrime(x); numprimes::numprimes+1; sum::sum+num; :[prime(sum!numprimes)=1; primes::primes,numprimes; primes::primes]; num}:~0; primes}
    

    findPrimes@365
    [5 6 7 8 12 15 16 19 20 21 24 26 30 34 37 38 40 42 44 45 46 48 49 50 55 58 59 60 62 64 65 66 67 68 70 72 73 75 76 78 86 87 88 92 102 116 120 122 124 128 130 132 135 140 143 145 150 156 158 164 165 166 168 172 173 175 176 182 183 191 196 210 214 216 218 223 234 236 241 248 250 256 259 262 265 266 272 280 285 301 306 310 311 314 315 324 328 330 336 337 344 347 348 349 352 355 358 365]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: