Programming Praxis

8 Responses to “Day 280”

1. Graham Enos said

   October 9, 2017 at 5:59 PM

   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. James Curtis-Smith said

   October 9, 2017 at 6:22 PM

   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

   October 9, 2017 at 8:38 PM

   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

   October 10, 2017 at 8:28 AM

   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

   October 10, 2017 at 1:11 PM

   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

   October 10, 2017 at 2:29 PM

   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

   October 13, 2017 at 8:23 PM

   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]
8. sealfin said

   December 25, 2017 at 11:14 AM

   October 9th, 2017.cpp:

   #include "seal_queue.h" /* <http://GitHub.com/sealfin/C-and-C-Plus-Plus/blob/master/seal_queue.h> */
   #include "printDateAndTime.h" /* <http://Gist.GitHub.com/sealfin/6d35f3a3958bd6797a0f> */
   #include <stdio.h>
   #include <limits.h>
   #include <stdlib.h>
   
   bool *g_isPrime = NULL;
   
   bool f_IsPrime( const unsigned short p );
   
   bool f_IsPrime( const unsigned short p )
   {
     if( p % 2 == 0 )
       return p == 2;
     else
       return g_isPrime[ p ];
   }
   
   int main( const int argc, const char * const argv[] )
   {
     unsigned short limit = 0;
     const unsigned short k_LimitStep = 1000;
     unsigned short i, number_of_primes, k, *primes, day = 1, number_of_days_sharing_characteristic = 0;
     seal_Queue<unsigned short> days_sharing_characteristic;
   
     #ifndef __MWERKS__
     printf( "\n" );
     #endif
     p_PrintDateAndTime();
     printf( "\n" );
   
     /* Firstly, let's determine (at least) the first 366 prime numbers; we're using a (slightly optimised) sieve of Eratosthenes, but an incremental sieve of Eratosthenes (as an example) would be more appropriate. */
     do
     {
       const unsigned int new_limit = limit + k_LimitStep;
   
       if( new_limit > USHRT_MAX )
       {
         fprintf( stderr, "Sorry, an error occurred: `limit` overflowed.\n" );
         if( g_isPrime != NULL)
           free( g_isPrime );
         exit( EXIT_FAILURE );
       }
       limit = new_limit;
       if( g_isPrime != NULL )
         free( g_isPrime );
       g_isPrime = ( bool* )malloc( sizeof( bool ) * limit );
       for( i = 0; i < limit; i ++ )
         g_isPrime[ i ] = true;
       number_of_primes = 0;
       g_isPrime[ 0 ] = false;
       g_isPrime[ 1 ] = false;
       for( i = 3; i < limit; i += 2 )
         if( g_isPrime[ i ] )
         {
           number_of_primes ++;
           for( k = i + i; k < limit; k += i  )
             g_isPrime[ k ] = false;
         }
     }
     while( number_of_primes < 366 /* Leap year. */ );
   
     /* Secondly, let's create a list of (at least) the first 366 prime numbers. */
     k = 0;
     primes = ( unsigned short* )malloc( sizeof( unsigned short ) * number_of_primes );
     primes[ k ++ ] = 2;
     for( i = 3; k < number_of_primes; i += 2 )
       if( g_isPrime[ i ] )
         primes[ k ++ ] = i;
   
     for( ; day <= 366 /* Leap year. */; day ++ )
     {
       unsigned int sum_of_primes = 0;
   
       for( i = 0; i < day; i ++ )
       {
         const unsigned long long new_sum_of_primes = sum_of_primes + primes[ i ];
   
         if( new_sum_of_primes > UINT_MAX )
         {
           fprintf( stderr, "Sorry, an error occurred: `sum_of_primes` overflowed.\n" );
           free( g_isPrime );
           free( primes );
           exit( EXIT_FAILURE );
         }
         sum_of_primes = new_sum_of_primes;
       }
       if( f_IsPrime( sum_of_primes % day ))
       {
         number_of_days_sharing_characteristic ++;
         days_sharing_characteristic.p_Push( day );
       }
     }
     free( g_isPrime );
     free( primes );
   
     printf( "There " );
     if( number_of_days_sharing_characteristic != 1 )
       printf( "are" );
     else
       printf( "is" );
     printf( " " );
     if( number_of_days_sharing_characteristic != 0 )
       printf( "%u", number_of_days_sharing_characteristic );
     else
       printf( "no" );
     printf( " day%s sharing the characteristic that on the Nth day, the sum of the first N primes, modulo N, is prime", ( number_of_days_sharing_characteristic != 1 )?"s":"" );
     if( number_of_days_sharing_characteristic > 0 )
     {
       printf( ": " );
       for( i = 0; i < number_of_days_sharing_characteristic; i ++ )
       {
         if( i > 0 )
         {
           if( number_of_days_sharing_characteristic != 2 )
             printf( ", " );
           if( i + 1 == number_of_days_sharing_characteristic )
           {
             if( number_of_days_sharing_characteristic == 2 )
               printf( " " );
             printf( "and " );
           }
         }
         printf( "%u", days_sharing_characteristic.f_Pop());
       }
     }
     printf( ".\n" );
   
     printf( "\n" );
     p_PrintDateAndTime();
     #ifndef __MWERKS__
     printf( "\n" );
     #endif
     exit( EXIT_SUCCESS );
   }

   Output:

   There are 108 days sharing the characteristic that on the Nth day, the sum of the first N primes, modulo N, is prime: 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, and 365.[/sourecode]

   On an Apple Power Mac G4 (AGP Graphics) (450MHz processor, 1GB memory) to run the solution took approximately one second on both Mac OS 9.2.2 (International English) (the solution compiled using Metrowerks CodeWarrior IDE 2.1 (Discover Programming Edition)) and Mac OS X 10.4.11 (the solution compiled using Xcode 2.2.1).

   (I’ve just completed a gig at London South Bank University and so I’m again just trying to solve the problems posed by this ‘site whilst I try to get a job (and I’ve solved this problem in particular to test my seal_Queue template class I might use in the fourth version of my SDL2 joystick interrogator utility); I’m well-aware that my solutions are far from the best – but, in my defence, I don’t have any traditional qualifications in computer science :/ )

   Ps. Merry Christmas, and thank you for running this ‘site!