Monday, September 12, 2016

Notes on Parker chains


This is a reponse to one of Matt Parker’s videos on his StandUpMaths YouTube channel at https://www.youtube.com/watch?v=LYKn0yUTIU4

Matt talked about a function defined for non-negative integers wherein the result is the number of letters in the name of the number.

For example,

`F(23) = 11` (11 letters in “twenty three”)
`F(11) = 6` (6 letters in “eleven”)
`F(6) = 3` (3 letters in “six”)
`F(3) = 5` (5 letters in “three”)
`F(5) = 4` (4 letters in “five”)

And that’s the end of the Parker chain, because `F(4) = 4`.

In English, all starting points eventually lead to 4.

Matt showed us that 23 is the lowest number that starts a Parker chain with a length of 6.

I am defining `C_n` as the lowest number starting a Parker chain of length n using the Parker algorithm.

`C_6 = 23`

Matt challenged us to find `C_7`, and to find any other interesting information about this algorithm, and to post any such findings as a comment on his video. I got a little bit carried away, and wrote a little more than will fit comfortably in a comment.

Assuming use of the short scale (for now) and not using the word “and”.

The longest number name under `10^30` is 373,373,373,373,373,373,373,373,373,373, or three hundred three hundred seventy-three octillion three hundred seventy-three septillion three hundred seventy-three sextillion three hundred seventy-three quintillion three hundred seventy-three quadrillion three hundred seventy-three trillion three hundred seventy-three billion three hundred seventy-three million three hundred seventy-three thousand three hundred seventy-three, with 321 alphabetic characters.

Therefore, in the longest possible Parker chain whose first number is `10^30` or lower, the second number in the chain is 321 or lower. All Parker chains starting with 321 or lower have 6 or fewer numbers in the chain. Therefore, the longest possible Parker chain whose first number is `10^30` or lower has a maximum of 7 numbers.

The first Parker chain of 7 numbers is 323, 23, 11, 6, 3, 5, 4.

`C_7 = 323`

How strange is that? Out of all of the possible starting numbers 30 digits or less, you only have to try as high as 323 to find an example Parker chain of the maximum possible length in that range.

As others have noted, the first Parker chain of 8 numbers has a starting number of just a bit over `10^30`.

`C_8 ~~ 10^30`

That’s a rather large gap.

Which makes me wonder, how large is the next gap?

Within each power of a thousand, the longest number name is approximately 32 letters longer than the longest number name in the previous power of a thousand. That’s an additional 24 letters for “three hundred seventy-three” and an average of 8 letters for the appropriate “*illion” for that power.

(There are many other, possibly infinite, numbers with the same name length, but a number with “373” repeating will be the lowest number of that name length.)

From that we can derive a simple formula to find the approximate location of the start of the next longer Parker chain.

`C_(n+1)` has as least `C_n` letters in its name. The first number with `C_n` letters in its name will be approximately

`C_(n+1) ~~ 10^(3/32 C_n)`

We can see this works for `C_7 = 323`.

`C_8 ~~ 10^(3/32 323)`
`C_8 ~~ 10^30`

And we can use that to estimate the size of the next gap.

At this scale, when `C_n` in is the form `10^x`, we can simplify the approximation.

`C_(n+1) ~~ 10^(3/32 10^x)`
`C_(n+1) ~~ 10^(1/10 10^x)`
`C_(n+1) ~~ 10^(10^(x-1))`

`C_9 ~~ 10^(10^(30-1))`
`C_9 ~~ 10^(10^29)`

That’s quite a gap.

Now we’re at a scale where we can simplify the approximation even farther, as our x in `10^x` is so large that subtracting one from it is a trivial difference. So for very large numbers:

`C_(n+1) ~~ 10^(C_n)`

From here on out, the gaps are easy to predict.

`C10 ~~ 10^(10^(10^29))`
`C11 ~~ 10^(10^(10^(10^29)))`
`C12 ~~ 10^(10^(10^(10^(10^29))))`
`C13 ~~ 10^(10^(10^(10^(10^(10^29)))))`

Now you may have noticed I made an assumption early on that you might take issue with. I am assuming an average of 8 letters for the name of each group of three digits, the so-called illion word. But it is actually reasonable.

As going to `C_9` takes us well beyond the range of numbers in any existing number naming system, we need a hypothetical number naming system that can handle these ridiculously large numbers. A reasonable extension of existing systems is possible.

To get up to `10^(10^29)`, we can’t just keep making up new illion words. We’ll run out of possibilities long before we get there. So we need something different. We already have something that can work, the so-called Long System previously used in Britain and still used in the rest of Europe and parts of Canada. We just need to follow it to a different logical conclusion than was done in the past.

Here is the Short System, used in the US, Britain and parts of Canada.

Short system
`1000^0``10^0`
`1000^(2^0)``1000^1``10^3`thousand
`1000^(2^1)``1000^2``10^6`million
`1000^3``10^9`billion
`1000^(2^2)``1000^4``10^12`trillion
`1000^5``10^15`quadrillion
`1000^6``10^18`quintillion
`1000^7``10^21`sextillion
`1000^(2^3)``1000^8``10^24`septillion
`1000^9``10^27`octillion
`1000^10``10^30`nonillion

Compare that to the Long System. I like the long system. Mathematically it is more logical, with major names based on powers of one million. And we can use it for much larger numbers without needing to add new words.

Short systemLong system
`1000^0``10^0`
`1000^(2^0)``1000^1``10^3`thousandthousand
`1000^(2^1)``1000^2``10^6`millionmillion
`1000^3``10^9`billionthousand million
`1000^(2^2)``1000^4``10^12`trillionbillion
`1000^5``10^15`quadrillionthousand billion
`1000^6``10^18`quintilliontrillion
`1000^7``10^21`sextillionthousand trillion
`1000^(2^3)``1000^8``10^24`septillionquadrillion
`1000^9``10^27`octillionthousand quadrillion
`1000^10``10^30`nonillionquintillion
`1000^11``10^33`thousand quintillion
`1000^12``10^36`sextillion
`1000^13``10^39`thousand sextillion
`1000^14``10^42`septillion
`1000^15``10^45`thousand septillion
`1000^(2^4)``1000^16``10^48`octillion
`1000^17``10^51`thousand octillion
`1000^18``10^54`nonillion
`1000^19``10^57`thousand nonillion
`1000^20``10^60`

But that only gets us twice as far, and we need to go much, much farther. Here is my hypothetical Really Long System. It starts the same as the long system, but more than one pattern can start from there, and I took the one less traveled by.

Short systemLong systemReally long system
`1000^0``10^0`
`1000^(2^0)``1000^1``10^3`thousandthousandthousand
`1000^(2^1)``1000^2``10^6`millionmillionmillion
`1000^3``10^9`billionthousand millionthousand million
`1000^(2^2)``1000^4``10^12`trillionbillionbillion
`1000^5``10^15`quadrillionthousand billionthousand billion
`1000^6``10^18`quintilliontrillionmillion billion
`1000^7``10^21`sextillionthousand trillionthousand million billion
`1000^(2^3)``1000^8``10^24`septillionquadrilliontrillion
`1000^9``10^27`octillionthousand quadrillionmillion trillion
`1000^10``10^30`nonillionquintillionthousand trillion
`1000^11``10^33`thousand quintillionmillion trillion
`1000^12``10^36`sextillionthousand million trillion
`1000^13``10^39`thousand sextillionbillion trillion
`1000^14``10^42`septillionthousand billion trillion
`1000^15``10^45`thousand septillionmillion billion trillion
`1000^(2^4)``1000^16``10^48`octillionthousand million billion trillion
`1000^17``10^51`thousand octillionquadrillion
`1000^18``10^54`nonillionthousand quadrillion
`1000^19``10^57`thousand nonillionmillion quadrillion
`1000^20``10^60`thousand million quadrillion
`1000^21``10^63`billion quadrillion
`1000^22``10^66`thousand billion quadrillion
`1000^23``10^69`million billion quadrillion
`1000^24``10^72`thousand million billion quadrillion
`1000^25``10^75`thousand trillion quadrillion
`1000^26``10^78`million trillion quadrillion
`1000^27``10^81`thousand million trillion quadrillion
`1000^28``10^84`billion trillion quadrillion
`1000^29``10^87`thousand billion trillion quadrillion
`1000^30``10^90`million billion trillion quadrillion
`1000^31``10^93`thousand million billion trillion quadrillion
`1000^(2^5)``1000^32``10^96`quintillion
`vdots`
`1000^(2^6)``1000^64``10^99`sextillion
`1000^(2^7)``1000^128``10^102`septillion
`1000^(2^8)``1000^256``10^768`octillion
`1000^(2^9)``1000^512``10^1536`nonillion

In the short system, with every new illion term added, we can count up through another power of a thousand.

In the long system, with every new illion term added, we can count up through another 2 powers of a thousand.

In the really long system, it’s an exponential growth rate. With every new illion term added, we can count up through the square of the previous word. That is, we double the number of powers of a thousand we can count through.

With this system, we only need 95 illion words (and a really long time) to count all the way up to `10^(10^29)`.

So this is a system that hypothetically would work.

In the table above, it looks like some of those names are quite a bit longer than 8 letters, but they are only used for a single group like that when talking about round numbers. For example, this number 1,000,000,000,000,000,000,000 would “one thousand million billion” but this number 1,002,003,004,005,006,007,008 would be “one thousand two million three thousand four billion five thousand six million seven thousand eight”

So with this system we do maintain an average of eight letters per power of a thousand group into very, very large numbers. Eventually we will be forced to start using longer illion words that will drive the average above 8 letters, but by then the approximate numbers we are describing will be so monstrous in size that the increase will be relatively trivial.

Saturday, June 18, 2016

Getting the current time from an NTP service using PowerShell

Recently I needed to be able to query the current time from an NTP service using PowerShell. I was surprised to find out that it wasn’t going to be easy.

There isn’t a simple-to-call way to do it. With modern Windows computers, you tell the operating system which NTP server to sync with, or let it sync with a domain controller or a Hyper-V host, and Windows does all of the doing automatically and invisibly.

But I was automating minimal configuration of thousands of brand new physical machines with a generic OS installed. My script needed to prepare them to successfully and securely talk to the system that would handle all of the configuration, domain join, etc. The challenge was the occasional new machine which, for whatever reason, had an internal clock that was far enough off that secure communications were being rejected. I wanted to add a simple piece of code that would query a corporate NTP service and set the system time, without modifying the machine’s NTP configuration.

After some searching, I found a script in the PowerShell Gallery name Get-NTPTime, written by Chris J Warwick. https://gallery.technet.microsoft.com/scriptcenter/Get-Network-NTP-Time-with-07b216ca

It’s a great script, but it outputs a lot more than I need, does a lot of work to create that output, is more precise than I need, and at over 500 lines (mostly comments) a bit too large to comfortably drop into my script.

So I heavily modified his script, ripping out everything I didn’t need, ripping out the high level of accuracy, and simplifying some of the syntax to make it easier for future engineers to support my script. The result is the reasonably concise function below.

There is no error handling in the function. It is presumed that error handling, if needed, will be handled at a higher level.

Our only parameter is a string with the (resolvable) name or IP address of the NTP service to query. We will assume the service is listening on port 123.

Function Get-NtpTime ( [String]$NTPServer )
{

We create an array of 48 bytes which we will use to hold our NTP request packet, and then reuse to hold the response packet.

$NTPData    = New-Object byte[] 48

We populate the first byte with the request header.

$NTPData[0] = 27 # Request header: 00 = No Leap Warning; 011 = Version 3; 011 = Client Mode; 00011011 = 27

We open a connection to the NTP service, setting timeouts so it doesn’t hang.

$Socket = New-Object Net.Sockets.Socket ( 'InterNetwork', 'Dgram', 'Udp' )
$Socket.SendTimeOut    = 2000  # ms
$Socket.ReceiveTimeOut = 2000  # ms
$Socket.Connect( $NTPServer, 123 )

Then we send the request and receive the results. Both of the .Send() and .Receive() methods output the number of bytes sent or received. We don’t need that output, so we’ll send those to $Null. Setting $Null equal to the result is much faster than piping to Out-Null, as PowerShell doesn’t have to waste the time and resources creating and handling a pipeline to nowhere.

$Null = $Socket.Send(    $NTPData )
$Null = $Socket.Receive( $NTPData )

Close the connection.

$Socket.Shutdown( 'Both' )
$Socket.Close()

The date/times in the response packet are in a weird epoch-based format. 4 bytes hold the number of seconds which passed between midnight of January 1, 1900, and the UTC time* represented. An additional 4 bytes hold a number which, when divided by 2^32, is an additional fraction of a second to a ridiculous precision.

In his version of this script, Chris uses two date/times in the response packet in conjunction with local times captured immediately before and after the query to calculate an extremely precise offset between the local system time and the NTP service time which even accounts for network latency.

I don’t need that level of accuracy; I just need to get it reasonable close. So instead of working with four time stamps, I am going to just use the first one in the response packet. And I am going to ignore the fraction of a second and any network latency. Most of the time, this will give me a time within one second of the NTP service time.

We can use the static .Net class [System.BitConverter] to convert the relevant 4 bytes into a single integer. We convert to UInt32 (unsigned integer) instead of Int32, because in this case the highest bit is set to one, and Int32 would interpret that as indicating a negative number rather than as part of the number itself. This gives us the number of seconds since 1/1/1900. (Who designs this stuff? Engineers are weird.)**

$Seconds = [BitConverter]::ToUInt32( $NTPData[43..40], 0 )

Lastly, we convert the number of seconds elapsed to the correct date time by creating a datetime object for 1/1/1900 and adding the seconds to it. Then we convert it from UTC to whatever the local time zone is, and return the result.

[datetime]'1/1/1900' ).AddSeconds( $Seconds ).ToLocalTime()
}

Using our function to set the system time can be as simple as this.

Set-Date ( Get-NTPDateTime $NTPServiceIPAddress )



Here is how it looks all together.

Function Get-NtpTime ( [String]$NTPServer )
{
# Build NTP request packet. We'll reuse this variable for the response packet
$NTPData    = New-Object byte[] 48  # Array of 48 bytes set to zero
$NTPData[0] = 27                    # Request header: 00 = No Leap Warning; 011 = Version 3; 011 = Client Mode; 00011011 = 27

# Open a connection to the NTP service
$Socket = New-Object Net.Sockets.Socket ( 'InterNetwork', 'Dgram', 'Udp' )
$Socket.SendTimeOut    = 2000  # ms
$Socket.ReceiveTimeOut = 2000  # ms
$Socket.Connect( $NTPServer, 123 )

# Make the request
$Null = $Socket.Send(    $NTPData )
$Null = $Socket.Receive( $NTPData )

# Clean up the connection
$Socket.Shutdown( 'Both' )
$Socket.Close()

# Extract relevant portion of first date in result (Number of seconds since "Start of Epoch")
$Seconds = [BitConverter]::ToUInt32( $NTPData[43..40], 0 )

# Add them to the "Start of Epoch", convert to local time zone, and return
[datetime]'1/1/1900' ).AddSeconds( $Seconds ).ToLocalTime()
}



* Irrelevant bonus fact: We use the abbreviation UTC because it is wrong in two different languages. In English, it should be CUT for “coordinated universal time”. In French, it should be TUC for “temps universel coordonné”. We compromised by agreeing to be universally uncoordinated with our time abbreviations.

** Irrelevant bonus fact 2: Storing date/times by using an Epoch-based system has been a common solution. For example, the .Net datetime objects we use in PowerShell store the number of ten millionths of a second since midnight of January 1 of the year 1. We lost a space probe to a short-sighted epoch-based system. On August 11, 2013, shortly after midnight, NASA's Deep Impact space probe, travelling between comets, stopped talking to us, because it was 2^32 tenths of a second after 1/1/2000. The clock rolled over, the probe thought it was suddenly 13 years earlier and it wasn’t due to check in again for over a decade.

Thursday, April 14, 2016

Call for a Microsoft PowerShell Czar

This is an open plea to Microsoft for the creation of the internal position of PowerShell Czar.

There is a PowerShell UserVoice suggestion to open source the AD module that is quickly accumulating votes. https://windowsserver.uservoice.com/forums/301869-powershell/suggestions/13350033-open-source-the-activedirectory-powershell-module

This is not users requesting a feature or a fix. This is exasperated users giving up hope that Microsoft will make basic improvements to the product.

There are too many teams at Microsoft that years ago came out with a reasonable (for the time) first version of the PowerShell module for their product, but have never followed up with v2. When they release a new version of their product, they make some minor changes to the PowerShell module that are related to new features in the core product. But they don’t understand that the PowerShell module is an integral part of their product, deserving of and requiring the same continuous improvement as the rest of their product, and it never matures past the level of barely good enough for a first release.

It has been ten years now, and too many teams at Microsoft have demonstrated that left to their own devices, they are not willing or able to produce the quality of PowerShell integration that we need.

Microsoft needs to create a PowerShell Czar. They can, of course, replace that silly title with one of the standard Microsoft silly titles, but the role would be the same.

The Czar would have the power to write and enforce PowerShell standards across the organization. The Czar would prevent releases from releasing if the PowerShell isn’t ready. The Czar would require teams to fill gaps in the PowerShell interface. The Czar would prevent desktop teams from locking in a pre-release version of PowerShell. The Czar would prevent teams from using non-standard parameter names and cmdlet names that are so long they wrap around the screen. The Czar would require implementations that are intuitive to PowerShell scripters, rather than to product architects. The Czar would require all MSDN articles about .Net objects to have PowerShell examples. The Czar would require MSDN articles about PowerShell .Net object be as complete as articles about other .Net objects. The Czar would require fixes to .Net objects that break PowerShell functionality that depends on them.

If Microsoft has another, less authoritarian way of accomplishing the same goals, fine, do it that way. But the current way is not working. This needs to be fixed. Microsoft, please make it happen.