Pseudoprimes To Bases 2 And 3

December 10, 2019

Regular readers know of my affinity for the Online Encyclopedia of Integer Sequences. I was browsing the other day and came across A052155, the sequence of pseudoprimes to both base2 and base3. This sequence is important because it forms the basis of a very fast primality test for numbers in the range 232 to 264, which is a very important range for some large factoring algorithms (particularly SIQS and NFS in their 2LP variants): a number n in range is prime if 2n-1 ≡ 1 (mod n), 3n-1 ≡ 1 (mod n), and n is not in a small list of known pseudoprimes to bases 2 and 3. The two modular exponentiations are reasonably quick, the lookup by binary search is even quicker, and the primality test is fully deterministic.

Your task is to calculate the pseudoprimes to bases 2 and 3 less than a million. 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

Muenchhausen Numbers

December 6, 2019

A radix-10 number is a Muenchhausen number if it is equal to the sum of its digits, each digit raised to the power of itself. For instance, 3435 is a Muenchhausen number because 3**3 + 4**4 + 3**3 + 5**5 = 3435. Strict Muenchhausen numbers do not permit 0 as a digit, because 0**0 is undefined. Variant Muenchhausen numbers permit 0 as a digit, with 0**0 defined as 0. Muenchhausen numbers also exist with radices other than 10.

Your task is to find all the Muenchhausen numbers in radix-10. 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

A Single Line Of Code

December 3, 2019

Today’s task challenges you write a useful program using only a single line of code. It is not fair to abuse the notion of a line. You can probably do more than you expect.

Your task is to write a useful program using only a single line of code. When you are finished, you are welcome to read a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

Happy Thanksgiving

November 26, 2019

My daughter is visiting this week, so there will be no exercises. The next exercise will be on Tuesday, December 3rd. Enjoy the time with your family.

I had a lot of fun working on this problem:

Given n, find x, y and z such that x y z = n and x + y + z is minimal; for instance, given n = 1890, the correct answer is (9 14 15).

Your task is to write a program to find x, y and z. 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

Modified Coin Change

November 19, 2019

We solved the standard coin change problem in two previous exercises. The particular problem given here is to find the minumum number of coins that can be used to create a target amount of money, given an unlimited number of coins of various denominations, and is normally solved by a dynamic programming algorithm.

Today’s task is a variant on that problem: find the minimum number of coins that can be used to create a target amount of money, given an unlimited number of coins of denomination that are powers of 5.

Your task is to write a program to solve the modified coin change problem. 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

Tri-Partitions

November 15, 2019

We have a fun little task for your Friday lunch hour:

Given an array of integers, rearrange the integers so no two consecutive integers have a sum that is divisible by 3, or indicate that such an arrangement is not possible.

Your task is to write a program to rearrange an array of integers as described 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.

Pages: 1 2

Reverse A Linked List

November 12, 2019

We’ve done this before, but I saw questions asked about this task on three different beginner-programming forums this weekend (it must that that time in the semester when teachers introduce linked lists), and it never hurts to do some basic drill.

Your task is to write a program that reverses a linked list. 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

Union Of Two Bags

November 8, 2019

Today’s exercise is somebody’s homework:

A bag is a list of key/count pairs: for instance, a bag containing three of item E, three of item R, and three of item A can be written E3R3A3. The union of two bags is a single bag containing a list of key/count pairs in which each item in each of the two bags has its count combined in a single item: for instance, the union of bags E3R3A3 and B3R3F3 is E3R6A3B3F3. The order of items in the bags is not significant.

Your task is to write three programs to compute the union of two bags, with time complexities O(mn), O((m+n) log (m+n)), and O(m+n), where m and n are the sizes of the two bags. 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

Encrypting Ed(1)

November 5, 2019

When I introduced the topic crypt(1) last week my actual goal was to write an editing script using ed on an encrypted file; that’s when I realized that crypt(1) was missing and that ed no longer had an -x flag. I didn’t want anything fancy, just basic encryption. I knew the old crypt(1) was no good (actually, it was no good when it was introduced forty years ago) but I was surprised that Unix and Linux had not kept up with some kind of encryption. Humbug!

Your task is to enhance ed by adding the -x encryption flag. 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