Posts

Chop off their heads and conquer the Pentagon (week 147)

Chop off their heads! Task 1 this week asks us to write a script to generate first 20 left-truncatable prime numbers in base 10. A left-truncatable prime (LTP) is a prime number which, in a given base, contains no 0, and if the leading left digit is successively removed, then all resulting numbers are primes. In principle this is easy enough: generate the primes using a sieve of our good friend Eratosthenes, discard any containing zeroes, and check the remainder for being left-truncatable.  I chose to exclude single digit primes, ie 2, 3, 5, and 7 because I felt that they did not meet the criterion of 'all resulting numbers are primes', because there are no resulting numbers. The next 16 LTPs are only 2 digits - they range from 11 to 97, and 4 more - 113, 131, 137 and 167 complete the required 20. The computing time is negligible. However, had the task asked for the first 1000, or 10 000 LTPs it would be worth applying a little optimisation.  For example, the last digit of an L

Large primes and curious fractions

The 10001st prime number  Task 1 for week 146 is a more of a challenge than in recent weeks: w e are asked to calculate the 10001st prime number. The first question to ask is whether the desired number can be represented as an integer in Perl. The largest number which Perl treats as an integer is given by ~1 + 1 and on my computer that is  18446744073709551615 or about 2 * (10**19).  Primes get a bit thin on the ground as they get larger, but I think we can safely postulate that we will find 10**5 of them before we hit that limit. My 'go to' algorithm for primes is the sieve of Eratosthenes.  Born in 276 BC, Eratosthenes was the first person to estimate the circumference of the earth - remarkably accurately - while managing the largest library in the world, in Alexandria. His sieve works like this. Write down all the numbers from 2 to however large you want - say n. Take the leftmost number - 2 - and rub out all its multiples - 2, 4, 6, 8 and so on.  Now do it again: the leftmo

How to find palindromes quickly

The challenge Write a script to create a Palindromic Tree for a given string: in other words to find all the unique palindromic substrings of the string. My solution I found the analysis in the referenced papers a little hard to follow, but maybe that was down to having eaten too much over Christmas.  So I developed my own algorithm which at least gives the right answer. I generated all possible substrings from the given string. So for a string of length n there are n substrings which are 1 character long, n-1 which are 2 characters long and so on up to 1 string which is n characters long. So there are n * (n + 1) / 2 substrings in all. For example, if the string is 'perl' the 10 substrings are  p pe per perl e er erl r rl l. Now I looped over these and checked (a) is it palindromic and (b) have I seen it before.  If the answer is (a) yes and (b) no, I record it as a valid item for the answer. The slightly tricky bit is the 'is it palindromic' question, because that'

Illuminating the Ulam

Perl Weekly Challenge 144, task 2 states: The challenge Write a script to generate Ulam Sequence having at least 10 Ulam numbers where $u and $v are the first 2 Ulam numbers. The first two numbers in an Ulam sequence are the lesser (U1) and the greater (U2) of $u and $v. Then for n > 2, Un is defined to be the smallest integer that is the sum of two distinct earlier terms in exactly one way, and larger than all earlier terms. The solution So how do we go about this?  If we know U1 to Un, how do we calculate Un+1? The initial thought is that we need to find the sums of all possible pairs, Uj and Uk, chosen from U1 to Un. Clearly, there are n(n - 1) such pairs, and we are looking for the one that: - exceeds Un, - is unique (ie the sum is not the same as any of the other sums), - is the lowest such number. We can cut the number of pairs to consider by half by insisting that Uj is less than Uk.  So our nested loops look some thing like: for j = 1 to n - 1 {     for k = j + 1 to n {     

Being stealthy is a fourfold property

PWC 143 task 2 involves stealthy numbers. A positive integer n is stealthy, if there exist positive integers a, b, c, d such that a * b = c * d = n and a + b = c + d + 1. The stealthy numbers less than 100 are: 4, 12, 24, 36, 40, 60, 72 and 84.  Looking further ahead it appears likely that there is an infinite number of such numbers.   Some stealthy numbers have more than one solution for a + b = c + d + 1, for example: n = 7200 72 + 100 = 75 + 96 + 1 75 + 96   = 80 + 90 + 1 n = 2520 35 + 72 = 36 + 70 + 1 40 + 63 = 42 + 60 + 1 42 + 60 = 45 + 56 + 1 All stealthy numbers are multiples of 4. The reason is this: Consider a + b = c + d + 1. Clearly either a + b or c + d must be an odd number, since they differ by 1. If a is odd, b must be even (so that a + b is odd), and c and d must either be both odd or both even (so that c + d is even). But we can rule out c + d being both odd, because c * d would then be odd and a * b would be even, so they cannot both equal n as is required. So, of a,

Clarity versus brevity

PWC 142 task 1: You are given positive integers, $m and $n. Write a script to find total count of divisors of $m having last digit $n. Tasks such as this always raise a dilemma.  Do I write something ingenious and compact, or should I write code which someone else (or me in 10 years) can easily understand. My submission falls in the second category. I simply loop $j from 1 to $m, checking whether $m / $j is an integer, in which case $j is a divisor. I add that to my list of divisors, and if it ends in $n, to my list of divisors ending in $n. This is - in once sense - quite inefficient, because o nce $j exceeds $m/2 the only remaining divisor is $m itself so I've wasted more-or-less half my time. I could get round that by looping $j from 1 to int($m/2), and every time I found a divisor $d I could add $d and $m/$d to my list of divisors. But then I would have to sort the list, or possibly make two lists, reverse one of them and concatenate, remembering that if $m is even, $m/2 will b

Some prime thoughts on divisors

Perl Weekly Challenge 141, task 1, reads: Write a script to find  lowest 10 positive integers  having exactly  8 divisors . The solution to this is easy enough in that all 10 numbers are less than 100. But what happens if we vary the number of divisors: find the lowest integer (k) having exactly n divisors?  The answers are as follows: n=>k 2 => 2 (1, 2) 3 => 4   (1, 2, 4) 4 => 6  (1, 2, 3, 6) 5 => 16  (1, 2, 4, 8, 16) 6 => 12  ( 1, 2, 3, 4, 6, 12) 7 => 64  ( 1, 2, 4, 8, 16, 32, 64) 8 => 24  ( 1, 2, 3, 4, 6, 8, 12, 24) 9 => 36  (  1, 2, 3, 4, 6, 9, 12, 18, 36) 10 => 48  ( 1, 2, 3, 4, 6, 8, 12, 16, 24, 48) 11 => 1024  ( 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024) 12 => 60  ( 1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60) 13 => 4096  ( 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096) 14 => 192  ( 1, 2, 3, 4, 6, 8, 12, 16, 24, 32, 48, 64, 96, 192) 15 => 144 ( 1, 2, 3, 4, 6, 8, 9, 12, 16, 18, 24, 36, 48, 72, 144) 16 => 120 ( 1, 2, 3, 4, 5