Yesterday’s post from Programming Praxis asks us to build a very special sort of expression. Using the numbers 10, 9, 8, 7, 6, 5, 4, 3, 2, and 1 in that order along with the operators of multiplication, division, addition, subtraction, and concatenation, find all of the ways that we can write an expression totaling 2013. Here’s one valid solution:
Yesterday’s post from Programming Praxis poses an interesting problem: find the largest prime n such that the result of repeatedly removing each digit of n from left to right is also always prime.
For example, 6317 would be such a number, as not only is it prime, but so are 317, 17, and 7.
Today’s post from Programming Praxis posits an interesting problem: how can we (efficiently) find all of the narcissistic numbers (in base 10)?
Based on this post from Programming Praxis, today’s goal is to write an algorithm that, given a number N and an alphabet A, will generate all strings of length N made of letters from A with no adjacent substrings that repeat.
So for example, given N = 5 and A = {a, b, c} the string abcba will be allowed, but none of abcbc, ababc, nor even aabcb will be allowed (the bc, ab, and a repeat).
It’s a little more general even than the version Programming Praxis specifies (they limit the alphabet to exactly *A = {1, 2, 3} *and more more general still than their original source which requires only one possible string, but I think it’s worth the extra complications.
Niklaus Wirth gave the following problem back in 1973:
Develop a program that generates in ascending order the least 100 numbers of the set M, where M is defined as follows:
a) The number 1 is in M.
b) If x is in M, then y = 2 * x + 1 and z = 3 * x + 1 are also in M.
c) No other numbers are in M.
(via Programming Praxis)
It’s an interesting enough problem, so let’s work out a few different ways of doing it.
After a sum of the first billion primes post (originally from Programming Praxis), I decided to finally write a segmented version of the Sieve of Eratosthenes.
Programming Praxis’ new challenge(s) are to write three different list algorithms three times, each with a different runtime complexity. From their first post last week we have list intersection and union and from a newer post yesterday we have the difference of two lists. For each of those, we want to be able to write an algorithm that runs in O(n2) time, one that runs in O(n log n), and finally one that runs in O(n). It turns out that it’s more of an exercise in data structures than anything (although they’re all still technically ’list’ algorithms), but it’s still interesting to see how you can achieve the same goal in different ways that may be far more efficient.
Yesterday had another programming puzzle by Programming Praxis. This time, we are looking for a very special sort of number, a Taxicab number. According to Wikipedia:
In mathematics, the nth taxicab number, typically denoted Ta(n) or Taxicab(n), is defined as the smallest number that can be expressed as a sum of two positive algebraic cubes in n distinct ways. – Wikipedia: Taxicab Number
This problem from Programming Praxis came about in the comments to my last post and intrigued me. So today, we are trying to sum the first one billion primes. Summing the first hundred, thousand, even million primes isn’t actually that bad. But it takes a bit more effort when you scale it up to a billion. And why’s that?
Yesterday’s new post from Programming Praxis asked us to find all triples (a, b, a+b) such that a and b are three digits and a+b is four and concatenating the numbers results in a pandigital number (one with all 10 digits). After that, find the smallest individual number in any of these triples.