Marsaglia’s Mental RNG

January 29, 2019

We saw an “in-your-head” random number generator in a previous exercise, but I found it hard to operate. Today’s exercise, due to George Marsaglia is a random number generator that even a dummy like me can work in his head:

Choose a two-digit number as a seed. Then form a new two-digit number by adding the ten’s digit and six times the unit digit. For instance, if you start from 23, the sequence is 23 → 20 → 02 → 12 → 13 → 19 → 55 → 35 …. Then the sequence of random digits is the unit digit of each two-digit number. This operation produces the numbers 1 through 58 as seeds; the ten digits each occur six times, except that nine and zero occur five times (because 59 and 60 are not part of the sequence).

Your task is to implement Marsaglia’s mental RNG, and experiment with it to determine its effectiveness. 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.

Pages: 1 2

First Word

January 25, 2019

We have a simple exercise today, inspired a co-worker. Where I work, we have a reporting tool that permits a “hook” to the underlying SQL in some places. My co-worker asked me how to write an SQL statement that extracts the first word (a maximal sequence of non-spaces) from the beginning of a string (assume there are no leading spaces). For instance, given the string “abcdefg hijklmnop qrs tuv wxyz” the first word is “abcdefg”. Here’s the SQL expression, wrapped in a select statement, with &&STR representing the string:

select substr('&&STR', 1, instr('&&STR', ' ') - 1) from dual

Your task is to write a program to extract the first word from a string. 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.

Pages: 1 2

Lunar Arithmetic

January 22, 2019

Over at Numberphile, Neil Sloane (yes, that Neil Sloane), talks about lunar arithmetic, an “other-worldly” way of doing simple math:

Lunar addition and multiplication work digit by digit, the same as terrestrial addition and multiplication, except that the plus and times tables are unusual. Addition is done by taking the larger of the two digits, so 1 + 3 = 3 and 7 + 4 = 7. Multiplication is done by taking the smaller of the two digits, so 1 * 3 = 1 and 7 * 4 = 4. Thus:

      3 5 7        3 5 7
    +   6 4      *   6 4
    -------      -------
      3 6 7        3 4 4
                 3 5 6
                 -------
                 3 5 6 4

There are no carries. There is no subtraction or division, since the results would not be unique.

Your task is to write programs that perform lunar addition and multiplication. 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.

Pages: 1 2

Extract Number From String

January 18, 2019

We have another string-handling exercise today:

Given a string containing a number, extract the number from the string. For instance, the strings “-123”, “-123junk”, “junk-123”, “junk-123junk” and “junk-123junk456” should all evaluate to the number -123.

Your task is to write a program to extract a number from a string. 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.

Pages: 1 2

Find The Difference

January 15, 2019

Today’s question comes from a programming student:

You are given two strings s and t that consist only of lower-case letters. String t was created by adding one letter chosen at random to string s, then shuffling the resulting string. Find the letter that was added to t. For instance, the difference between the two strings “abcdef” and “bfxdeac” is the character “x”.

Your task is to write a program to find the random letter that was added to the string. 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.

Pages: 1 2

Parallel Assignment

January 11, 2019

Recently, I was writing a program where I needed parallel assignment; the details of my program don’t matter. Some languages provide parallel assignment natively; for instance, Python:

Python 2.7.13 (default, Mar 13 2017, 20:56:15)
[GCC 5.4.0] on cygwin
Type "help", "copyright", "credits" or "license" for more information.
>>> a,b,c = 1,2,3
>>> print a,b,c
1 2 3
>>> a,b,c = b,c,a
>>> print a,b,c
2 3 1

You can do something similar in C (I think — I’m not sufficiently expert in C to be certain this works):

#define SWAP(x, y) { typeof(x) t = x; x = y; y = t }

Your task is to add parallel assignment to your favorite programming language. 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.

Pages: 1 2

Perfect Totient Numbers

January 8, 2019

A perfect number is a number for which the sum of its proper divisors is equal to the number; for instance, 28 is a perfect number because it is the sum of its proper divisors 1 + 2 + 4 + 7 + 14 = 28.

A perfect totient number (A082897) is a number for which the sum of its iterated totients is equal to the number. For instance, 327 is a perfect totient number; its iterated totients are φ(327) = 216, φ(216) = 80, …, and the sum of 216 + 80 + … = 327. I love number theory; it’s totally useless, and endlessly fascinating, as you will see if you follow the links on OEIS.

Your task is to compute the perfect totient numbers less than 10,000. 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.

Pages: 1 2

[ I worked half-time during December, still suffering fatigue, then during the Christmas break I visited my daughter in Houston; I’m back at work full-time now. Thanks to all for your good wishes. ]

Numberphile has a short episode about self-locating strings in π; for instance, if you ignore the part before the decimal point and number the digits of π starting from zero, the sixth digit of π is 6 and the two digits starting at the 27th digit are 27.

Your task is to write a program that finds self-locating strings in π (A064810). 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.

Pages: 1 2