Triangle Of The Gods
November 10, 2015
The nth element of the Smarandache consecutive number sequence (A007908) is the sequence of the numbers from 1 to n concatenated in order:
1, 12, 123, 1234, 12345, 123456, 1234567, 12345678, 123456789, 12345678910, 1234567891011, 123456789101112, …
The sequence is sometimes called the “Triangle of the Gods,” and the story goes that anyone who can specify the smallest prime number in the sequence is admitted to heaven.
Your task is to find the smallest prime number in the sequence. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Self-Organizing Lists
November 6, 2015
There are many applications where you need to keep a small number of items, a set, and check for membership in the set, and there are many algorithms for doing that: a linked list keeps the items in random order to be retrieved by linear search, an ordered array keeps the items in sequence to be retrieved by binary search, a hash table performs some kind of math on the item, various kinds of trees can store and search the items, and so on.
Today’s exercise looks at a simple algorithm that is appropriate for search in a set that isn’t too big, doesn’t change too often, and isn’t searched too many times, where the definition of “too” depends on the needs of the user. The idea is to store the items of the set in a linked list, search the list on request, and each time an item is found, move it to the front of the list. The hope is that frequently-accessed items will stay near the front of the list, so that instead of an average search that requires inspection of half the list, frequently-accessed items are found much more quickly.
Your task is to write functions that maintain a set as a self-organizing list: you should provide functions to insert and delete items from the set as well as to search within the set. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
School Awards
November 3, 2015
This counting problem appears from time to time:
There is a school that awards students who, during a given period, are never late more than once and who are never absent for three or more consecutive days. How many permutations of on-time, late and absent, with repetition, are possible for a given timeframe that will result in an award being given to a particular student. For instance, for a three-day timeframe there are 19 ways in which a student can win an award.
Your task is to solve the counting problem given above. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Reverse String Ignoring Special Characters
October 30, 2015
Today’s exercise solves a homework problem for some lucky reader:
Given an input string that contains both alphabetic characters and non-alphabetic characters, reverse the alphabetic characters while leaving the non-alphabetic characters in place. For instance, given the input string
a!b3c, return the output stringc!b3a, where the non-alphabetic characters!and3are in their original positions.
Your task is to write a program that reverses a string while leaving non-alphabetic characters in place. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Strangers On A Train
October 27, 2015
In Sloane’s Encyclopedia, sequence A247665 is defined as
a(1) = 2; thereafter a(n) is the smallest number not yet used which is compatible with the condition that a(n) is relatively prime to the next n terms. The sequence begins 2, 3, 4, 5, 7, 9, 8, 11, 13, 17, 19, 23, 15, 29, 14, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, …
The sequence was submitted by Amarnath Murthy and given to Neil Sloane as a birthday present. Sloane calls the sequence “Strangers on a Train” after the psychological thriller novel by Patricia Highsmith and subsequent film by Alfred Hitchcock, because the nth element of the sequence has no factors in common with the next n elements (they are “strangers”).
Your task is to write a program that generates the sequence. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Two Swaps
October 23, 2015
Today we have one of those tricky interview questions that are easy once you know the answer:
You are given an array of three elements, in some random order. You must sort the array into increasing order, but may only use two swaps. How can you do it?
Your task is to write a program that sorts a three-element array with only two swaps. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Longest Sequence Of Consecutive Odd Integers
October 20, 2015
Today’s exercise is to find the longest sequence of consecutive odd integers that add to a given sum. For instance, given the target 160701, the three consecutive odd integers 53565, 53567 and 53569 sum to 160701, but the 391 consecutive odd integers from 21 to 801 also sum to 160701, and are the longest sequence of consecutive odd integers to do so, so they are the correct answer.
Your task is to write a program to find the longest sequence of consecutive odd integers that add to a given sum. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Largest Possible Remainder
October 16, 2015
The result of dividing a number n by a divisor d is a quotient q and a remainder r. Given a fixed n and a divisor d in the range 1 ≤ d < n, find the divisor that produces the largest possible remainder. For instance, given n = 20 and 1 ≤ d < 10, the largest remainder is 6 when the divisor d is 7.
Your task is to write a program that finds the largest possible remainder. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Double Double Words
October 13, 2015
Today’s task is to write a program that reads a file and reports any instances of doubled words, which is a useful program for anyone that does a lot of writing, as I do in this blog.
Your task is to write a program to find doubled words. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Searching For Hypotenuses
October 9, 2015
Hypotenusi?
Your task is to write a program that returns all the numbers less than some limit (think somewhere in the millions or tens of millions) that can be the hypotenuse of a right triangle with integer sides; strive for the minimum possible run time for your program. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Programming Praxis 