Category Archives: Uncategorized

Targeting Skills Needs in Regions

Tools of trade

Targeting Skills Needs in Regions was the name given by the Australian Government to a program that was intended to alleviate a critical shortage of skilled labour in some regions of Australia.

A report on the evaluation of the program was recently published by the Australian Government Department of Education, Employment and Workplace Relations. A copy of the report can be downloaded from here. The copy was obtained from http://www.deewr.gov.au/Skills/Resources/Publications/Pages/RegionalSkills.aspx on 21 December 2011 at 02:31 hrs.

Multidose vials of influenza vaccine: views on risk

Australian Doctor recently published a discussion article on the use of multidose vials for influenza vaccine. The discussion follows on from the publication in the Medical Journal of Australia of an article by Angela O’Brien-Malone and me regarding some of the medico-legal aspects of the use of the vials. The Australian Doctor article is particularly interesting because it presents a several competing points of view, with some practitioners arguing for the use of the vials, and others against.

A PDF copy of the article is available here.

Preventing a line hang-up: how often must you speak?

Consider the following problem. You have made a connection to a machine to which you want to transfer some data. You know that if you are silent for some finite, but unknown time, then the machine will hang-up on you. To keep the line open, you need to ‘ping’, or speak to, the machine at the other end. How often do you need to speak?

How can I force my ISP to give me a new IP address?

An alternative way of thinking about the problem is in terms of the lease time for an IP address that has been assigned by a DHCP server. Unless you have been assigned a permanent IP address by your internet service provider (ISP), then it is possible that each time you connect to the network, the DHCP server will assign you a new IP address. Typically, however, short disconnections from the network followed by reconnection will not result in a change of the IP address. In particular, if you reconnect to the network within the so-called ‘lease time’ of the IP address, then the address will be unchanged. If you reconnect after the expiry of the lease then the IP address that you are assigned from the pool of available addresses is likely to be (but is not guaranteed to be) different from the previously assigned address. How do you discover the lease time that the DHCP server uses? It’s a question that clearly interests a great many users although their question is usually phrased as ‘How do I change my IP address?’, or ‘How do I force my ISP to give me a new IP address?’

Phrased that way, the answer is, of course, that you can’t force the ISP. What you can do is to disconnect from your ISP for a duration that exceeds the the DHCP lease time of the IP address. But that begs the original question.

Analysis

I have not seen any literature related to the problem and I was surprised to learn, from my own analysis, just how time-expensive it is to pinpoint the lease time with any accuracy. I considered the following two, mutually exclusive possibilities: (a) I have a certain (as in sure) upper-bound for the lease-time, or (b) I have no idea of the lease time. If one were only reasonably sure, for example, that the lease-time is a couple of hours but were nonetheless absolutely certain that it could not exceed a year, then the situation would still meet the criterion for Scenario-a. I also make an important assumption that might, in fact, not be strictly true of the DHCP protocol. Specifically, I assume that by reconnecting to your ISP, the timer for the line will be reset so that the amount of lease-time that has expired on reconnection is zero.

Binary search strategy

The strategy that I examined relating to each of the two possibile scenarios was essentially one of binary search. However, it is a kind of binary search quite unlike those that are normally described for solving problems such as finding an entry in a database. What I used was an approach that seems intuitively obvious although I have no proof of its optimality.

Imagine that you know for certain that the lease time is less than a week. You might then try disconnecting from your ISP for half a week and, if your IP number remains unchanged, try disconnecting for three-quarters of week. If that then proves to be successful in changing the IP address, you might try disconnecting for 5/8 of a week, and so forth. The difference between this strategy and a normal binary search on a random-access machine is that ‘time’ does not have a random-access feature! Even worse, it does not have a rewind feature as a tape drive would. To improve on your upper-bound for the lease time of three-quarters of a week, you cannot simply rewind by 1/8 of a week to test the effectiveness of a 5/8-week disconnection. Instead you have to restart from time zero.

Experiments

For any given lease time that is less than the lease-time’s upper-bound, there is a specific total time—the discovery time— that it will take you to discover that that time is indeed the lease time. For example, assume that you know that 1024 time-units provides an upper bound on the lease time; that is, you know that the actual lease time is strictly less than 1024 time-units. Imagine also that the actual (but unknown) lease time is 73 time-units; in other words, 73 is the number that you are wanting to discover. The discovery process would proceed as an iteration of: (a) connection, (b) waiting, (c) checking whether a new IP number has been assigned, (d) increasing or decreasing the waiting time appropriately, and (e) disconnection. The waiting time (discovery) sequence would be: 512 units (half the upper bound), 256, 128, 64, 64 + 32 = 96, 64 + 16 = 80, 64 + 8 = 72, 64 + 8 + 4 = 76, 64 + 8 + 2 = 73, 64 + 8 + 1 = 73. The total time spent on the discovery process would then be 1431 time units … far greater than I would have guessed prior to doing the analysis.

I determined what the total discovery time would be for each (integer) lease time between 1 time-unit and 1023 time-units on the assumption that (Scenario 1) I knew that 1024 was an upper bound for the lease time, or (Scenario 2) I had no information regarding an upper bound.

The red line in the graph above shows the relationship between lease-time and discovery-time for Scenario 1. There are several things to note. First, the discovery time increases monotonically, though not strictly monotonically, with lease-time. For example, it takes as long (1577 time units) to pin-point a lease-time of 103 units as a lease-time of 104 units. Second, one can see that the red line does not intersect the origin, indicating that there is some fixed (time) cost for the discovery process, even if the lease-time proves to be very short. In fact, using the strategy that I’ve described it will cost 1023 time units to discover that the lease time is 1 time unit when the only available prior information is that the lease-time upper bound is 1024 and, in general, costs 2n–1 time-units to discover that the lease time is of duration 1 when the only known upper bound is 2n.

The violet line in the graph above shows the relationship between lease-time and discovery-time when there the upper-bound on the lease-time is unknown. The strategy that is assumed here is to begin with a disconnection of 1 time-unit and if that is unsuccessful in producing a change in IP address, disconnecting for 2 time-units, and then 4 time-units, and so forth, until a new IP address is obtained. Once that has been achieved, one has succeeded in obtaining a previously unknown upper-bound on the lease-time and one proceeds with a binary search following the strategy described for the scenario where the upper bound is known. As one can see from the graph, the times are short at the low end, but grow fast. In fact, the time-complexity for the case where there is no known upper-bound is O(n log n), as shown by the plot of the function n log2n (blue curve).

Keywords

DHCP, lease time, binary search, IP address

Contributors

Mark R. Diamond

Multiplicative persistence: new null results

Multiply together all the digits of a positive integer, n. Using the result, repeat the digit-multiplication process to obtain a new result. Continue until a single digit result is obtained. The number of steps, p, that it takes for n to be changed to the single digit end-point, is called the multiplicative persistence of n. (Sloane, 1973).

It is widely believed that there is no integer in base-10 that has a multiplicative persistence greater than 11. On several websites there is appears an assertion to the effect that any number with multiplicative persistence greater than 11 must have more than 3000 decimal digits—see, for example, this page at the University of Waterloo. However, I have been completely unable to trace the origin of the assertion. The Mathworld entry on multiplicative persistence refers to the work of Phil Carmody in 2001, and, more modestly, states that the lower bound on a number with persistence greater than 11 is 10233. That provides the background to what follows here.

I used Mathematica to extend the range of known results by testing the multiplicative persistence of all those numbers that can be represented as strings of up to one thousand 2s, one thousand 3s, and one thousand 7s, or as strings of up to one thousand 3s, one thousand 5s, and one thousand 7s. To see why these numbers are of particular interest, see the main paper.

My main result is the null result. None of the integers that I tested, other than those already known, had a multiplicative persistence greater than or equal to 11. Of course, if there is already a genuine basis for the assertion regarding a lower bound of 103000 on a persistence 12, then I have unnecessarily wasted a few hours of computer time!

Almost all of the 1,000,000,000 numbers that I tested (products of powers of 2, 3, and 7, and products of powers of 3, 5, and 7) had a persistence of 2. Put another way, most numbers represented by strings of up to one thousand 2s, one thousand 3s, and one thousand 7s, or by strings of up to one thousand 3s, one thousand 5s, and one thousand 7s, have persistence 3.

An ASCII file of the complete results (omitting those power products with persistence 2) can be downloaded from here. The file is surprisingly small. The rows represent numbers of the form 2j × 3k × 7l and of the form 3j × 5k × 7l. The exponent of 2 is in columns 1–4, column 5 is blank, the exponent of 3 is in columns 6–9, column 10 is blank, the exponent of 5 is in columns 11–14, column 15 is blank, the exponent of 7 is in columns 16–19, column 20 is blank, and the multiplicative persistence of the number formed as the product of the powers of 2, 3, 5 and 7 is shown in columns 21–24. You can also download a Mathematica notebook that produces the results.

References

[1] Sloane, N J. A. (1973). The persistence of a number. Journal of Recreational Mathematics 6, 97–98.
[2] Diamond, M. R., & Reidpath, D. D. (1998). A Counterexample to Conjectures by Sloane and Erdos Concerning the Persistence of Numbers, Journal of Recreational Mathematics 29, 89–92.

Contributors: Mark R. Diamond

Gaming your way to non-trivial results

In 2005, in a posting on Reality War Games, I suggested the possibility that a well equipped military might create an on-line game that recruited gamers from around the world to participate in the simulation of a planned, real-life, military offensive. Something of much the same kind has just been announced in a paper (doi:10.1038/nsmb.2119) published in the journal, Nature Structural and Molecular Biology.

Online players of the protein folding game Foldit were awarded points for producing progressively more accurate models of the protein known as M-PMV retroviral protease. Players scored points according to the energy state of the protein fold that they produced. The lower the energy state of the folded protein, the higher a player’s score. The Foldit players were able to generate models of sufficient quality that it was then possible to build on those models to determine the actual structure of the protein. So, the idea no longer seems so remote that the next massively parallel multi-player online game that you join will actually be a rehersal for World War III.

References

Khatib, F., Dimaio, F., Foldit Contenders Group, Foldit Void Crushers Group, Cooper, S., Kazmierczyk, M., Gilski, M., Krzywda, S., Zabranska, H., Pichova, I., Thompson, J., Popović, Z., Jaskolski, M., & Baker, D. (2011). Crystal structure of a monomeric retroviral protease solved by protein folding game players. Nature Structural and Molecular Biology, doi: 10.1038/nsmb.2119

Contributors: Mark R. Diamond