Technical problem to solve - Function over range using sum of digits.

This apparently simple problem has been fascinating me for a long while now. The question is

For all the numbers n between 0 and 1E18  that's  1*10^18 or 1 with 17 zeroes how many have the property :

Sd(n) = Sd(137 * n)

where the function Sd( ) or sd ( ) is the arithmetic sum of the digits of the number in brackets.

For examples

• Sd(81) = 8+1 = 9        and  Sd(81*137)   = Sd(11097) = 18 Function is Not true
• Sd(369)= 3+6+9 = 18 and  Sd(369*137) = Sd(50553) = 18 Function is True = *Bingo*

Going directly to the answer by counting from 0 to 1E18  ( 1 with 18 "0"s after) and working out which of the numbers that have the property is possible but not really feasible.  Using 1000 processors each working in parallel on a separate range with 10^9 numbers would take an hour or so once set up.  GPUs using CUDA would provide such compute resources at an affordable price but do require specialist programming. However brute forcing the answer is not usually the best way. A hint can be taken from the question that there is an alternative method to solve this problem. The question asks “how many” rather than “which numbers” have the property. This opens the possibility that the quantity of numbers can be found without looking at every possible candidate in the range.

By the way 137 is a prime number but not sure if that is relevant.

The term "Bingo" indicates a number that has the property.

Analysis Step 1 - Very approximate answer

Working out the function for the a few ranges of numbers is not so hard and gives these results:

Analysis is started by using a sample of numbers 0..999999 to see if an approximate answer can be determined statically. When starting the count in the range 0..10 we find  0 is a bit of an exception but does have the property 

sd(0) = sd(137*0) as 0 = 0,
also sd(9) =  as sd(137*9) = 1+2+3+3 = 9

Looking in larger ranges

After 0 the occurrence of the property is less predictable but a possible clue is found. The trend is towards their being about 2.7 % of numbers having the property.

Analysis Step 2 - Make a distribution picture

Creating spreadsheet that compares/counts the results of sd(n) along the top and sd(137 * n) along the rows we can pick out (in red boxes ) and count where sd(n) = sd(137 * n)
Contents are coloured by number of occurrence between 1..1,000,000

To see how the sd() function works in Excel - see nearby blog entry.

 From this distribution picture we can confirm that the combined cells with the property sd(n) = sd(137n) have 27955 entries. We can also see that the cells where sd(n) = sd(137n) are all in columns sd(n) and rows sd(137*n) that are divisible by 9 ie: 9, 19, 27, 36, 45, 54.

Analysis Step 3 - Look for patterns in the reachable answers

Generating a script to output the numbers and find the occurrences helped check for patterns.

The columns of this output are

n     - The number

%06d  - the number using 6 digits with leading zeros

137*n - The number * 137

sd(n) - Sum_of_digits in n

sd(137n) - Sum_of_digits in n * 137

n%9==0 - does n Modulo 9 = 0, Modulo '%' is the remainder after n is divided by another number.  Examples  5 % 2 = 1 and 99 % 9 = 0.

sd(n) == sd(137*n) - Is the property true for this value of n y/n

Output spacing and colouring adjusted for clarity.

#n, %06d, 137*n, %06d, sd(n),sd(137n),n%9==0?, sd(n)==sd(137n)?, !

0,000000,0,   000000,0, 0,y,y,!

1,000001,137, 000137,1,11,n,n,!

2,000002,274, 000274,2,13,n,n,!

3,000003,411, 000411,3, 6,n,n,!

4,000004,548, 000548,4,17,n,n,!

5,000005,685, 000685,5,19,n,n,!

6,000006,822, 000822,6,12,n,n,!

7,000007,959, 000959,7,23,n,n,!

8,000008,1096,001096,8,16,n,n,!

 ...

87,000087,11919,011919,15,21,n,n,!

88,000088,12056,012056,16,14,n,n,!

89,000089,12193,012193,17,16,n,n,!

90,000090,12330,012330, 9, 9,y,y,!

91,000091,12467,012467,10,20,n,n,!

92,000092,12604,012604,11,13,n,n,!

 ...

98,000098, 13426,013426,17,16,n,n,!

99,000099, 13563,013563,18,18,y,y,!

100,000100,13700,013700, 1,11,n,n,!

101,000101,13837,013837, 2,22,n,n,!

Takes about 10 seconds to run the first 1 million numbers.  Looking at just the numbers where the property is true enables an apparent breakthrough. Notice that the the last two y/n fields are both set if the number % 9 = 0 and if the sum_of_digits property is true.

$ perl run_cols.pl | grep 'y,!' | head

  0,000000,0,000000,0,0,y,y,!

  9,000009,1233,001233,9,9,y,y,!

 90,000090,12330,012330,9,9,y,y,!

 99,000099,13563,013563,18,18,y,y,!

198,000198,27126,027126,18,18,y,y,!

279,000279,38223,038223,18,18,y,y,!

369,000369,50553,050553,18,18,y,y,!

387,000387,53019,053019,18,18,y,y,!

396,000396,54252,054252,18,18,y,y,!

…..

22653,022653,3103461,3103461,18,18,y,y,!

22680,022680,3107160,3107160,18,18,y,y,!

22689,022689,3108393,3108393,27,27,y,y,!

22698,022698,3109626,3109626,27,27,y,y,!

22716,022716,3112092,3112092,18,18,y,y,!

It was seen that every number that had the sum_of_digits property also had the n % 9 = 0  property. The last two y/n columns show this. Unfortunately not all numbers that have the n % 9 = 0  have the sum_of_digits property.   

 1365  history

$ perl run_cols.pl | grep 'n,n' | wc -l

  888888

$ perl run_cols.pl | grep 'y,n' | wc -l

   83157

$ perl run_cols.pl | grep 'y,y' | wc -l

   27955

$ perl run_cols.pl | grep 'n,y' | wc -l

       0

888888+83157+27955 = 1000000 - All lines 0..999999 accounted for

888888 numbers have neither of sum_of_digits property or n % 9 =0

83157 numbers have %9=0 but not the sum_of_digits property.

27955 have both %9=0 and the sum_of_digits property.

0 numbers that have  %9=0 do not have sum_of_digits property.

This confirms a hint where by only the numbers that have the %9=0 property need to be checked for the sd(n) = sd(137n) property.  %9=0  represents 10 percent of the numbers in any given number range.

However there still remains the need to check 1*E18 numbers.

Analysis Step 4 - Split and conqure 

Here is where things get interesting and just a bit more complex. How do we scale up to be able to get the answer across the whole target range of 0 to 1E18 ?  Any number x that starts with 1 and is only followed by 0s (eg. 10, 1000, 1000000000 ) would not be a Bingo as x % 9 = 1.  We can therefore safely adjust the range to ( 1E18 ) -1  ie 17  digits all 9s in a row.

Given that it is quite feasible to do the test every number up to about 8 or 9 digits lets look into methods for treating the larger numbers as two shorter numbers.  Working an example number 7317007327 lets split the digits into two 6 digit numbers and call them M & L.  We have  M=73170 and L=007327.

M, L                          = 007317, 007327

sd(M), sd(L)              = 18, 19 = 37

M*137 , L*137         =  1002429 , 1003799
Treated separately 

sd(M*137 ), sd(L*137)  =  18 , 29  added together are 47

which would indicate the sd(M.L) = 37 is not equal to  sd(137 M.L) = 47 for this value of M & L. However we can use these numbers to test alternative handling of split numbers.

There is an apparent flaw in the above process that can be seen when M & L  are recombined into a single number:

n = 007317007327

sd(n) = 37
137n = 1002430003799
sd(137n) = 38

gives 37 & 38, the property is not satisfied. The split method above is not giving the same answers which it would if the split method was correct.

We cans that splitting a big multi digit numbers into parts and treating those parts independently is not going to work without some carry over adjustments. As L*137 = 1003799 gives a 7 digit result there is carry over of 1 from L*137 into M. Should this carry be added before or after M is * 137?

Using . to represent textual concatination and M & L as the two textual halves of a number sd(M.L) == sd ( 137 * ( M.L) )  

is calculated as

sd(007317) + sd(007327)              = 18 + 19  = 37

then

sd(M) + sd(L)  ==  sd( 137 * M + car( L*137 ) ) + sd( bot(L*137) ) 

where car(  ) is the carry digits from 137*M and  bot(  ) are the remaining digits after carry digits have been removed.

Working this on 007317007327 we start with M as 007317 and L as 007327.

From L*137 = 1003799  we get car( L*137 ) = 1 and bot(L) is 003799

Before
= sd( 137 * ( M + car( L*137 ) )) + sd( bot(L*137) )
= sd( 137 * ( 007317 + 1)) + sd( 003799 ) 

= sd( 137 * 7318 ) + 28

= sd(1002566) + 28
= 20 + 28
= 48  which does not matches with sd(137 * 7317007317) = sd(1002430003799) = 38

After
= sd( 137 * M + car( L*137 ) ) + sd( bot(L*137) )
= sd( (137 * 007317) + 1)) + sd( 003799 ) 

= sd( 1002429 + 1 ) + 28

= sd( 1002430) + 28
= 10 + 28
= 38  which matches with sd(137 * 7317007317) = sd(1002430003799)

The property is still not satisfied as 37 not equal to 38 but at least we have consitent results when calculating sd(137 * n ) = 38 using the split number method with carry added in after multiplication.

Analysis Step 5 - Memorise and join 

Having shown that we can handle big numbers by splitting in two the next task is to rework 2 * 9 digit numbers using a memorised table of results to join the 2 halves.

... TBC

Updated 10:00 - 10 April 2018

PS Perl "Feature"

Doing the exploration of the investigation above, a language features of Perl came to prominence. Many of the calculations involved taking the textural representation of a number and summing the digits for the sd() function.   For sd(312023) = 11. We also split the text string and interpreted those as numbers. 312023  => 321 and 023. Perl is generally quite forgiving about moving between strings and integers but unfortunately this stumbles on a feature from the dark ages of computing. 

Consider 

perl -e 'print 312023," ",312," ",23,"\n";'

312023 312 23

and

perl -e 'print 312023," ",312," ",023,"\n";'

312023 312 19

In the second example the third part "023" is interpreted as octal ( base 7 ) and becomes 2*8+3 decimal 19.  Similarly 0x23 would be interpreted as hexadecimal giving decimal 35. This took some hunting down.

Sum of digits function in Excel and perl. sd(n)

In Excel

From : http://www.listendata.com/2013/02/excel-sum-of-digits-in-number-using-non.html

01. Formula - Sum & Index

Assuming a value is entered in cell B4 i.e. 45454. The sum of the digits of this number is 22.

=SUM(INDEX(1*(MID(B4,ROW(INDIRECT("1:"&LEN(B4))),1)),,))

02. Formula - Sumproduct & Indirect

Assuming a value is entered in cell B4 i.e. 45454. The sum of the digits of this number is 22.

=SUMPRODUCT(MID(B4,ROW(INDIRECT("1:" & LEN(B4))),1)*1)

03. Formula - Sumproduct & Indirect

Assuming a value is entered in cell B4 i.e. 45454. The sum of the digits of this number is 22.

=SUMPRODUCT(MID(B4,ROW(OFFSET($A$1,,,LEN(B4))),1)+0)

04. Formula - Array Formula

For the people who enjoys hitting Ctrl Shift Enter. Assuming a value is entered in cell B4 i.e. 45454. The sum of the digits of this number is 22.

=SUM(MID(B4,ROW(INDIRECT("1:" & LEN(B4))),1)*1)

Note : Press F2 and Hit Ctrl Shift Enter to confirm the above array formula.

In Perl 

sub sd() {

#sum of digits

local $t =0;

        map { $t+= $_; } split //,$_[0];

        return $t;

}

This subroutine splits the first argument $_[0]  into a digits array then adds the elements of the array by maping over the elements.   1234 => 1,2,3,4 => 1+2+3+4 => 10.

Adoption Story - Reunion after 57 years. 3/2 - Other FAQ and advice.

Just a round up of other FAQs arising.

Where can I read more ?  Adoptions prior to 1975 had different rules than after 1975. Major reforms in this area of law occurred in December 2005.  See Adoption information search information here. Excellent page with lots of information from http://www.adoptionsearchreunion.org.uk/Channels/ 

Where is the official uk contact register ? The UK passport office hold the adoption contact register for parents, sibling and adoptees who which to contact or not contact birth relatives. The PO runs a passive contact register and does not do active searches.  Some online sites offer this service as well but I have not explored or offer advice on them. See also the UK General Register office - for official birth/marriage/death records.

Where can I get advice ? Many UK local councils have adoption services with an adult section. These are probably under-funded and very busy but they do have a stature duty to provide contact counselling for pre 1975 adoptees.

Should I contact my birth relatives ?   No one can make that decision except you. This is one of life's difficult one-way choices. When you feel emotionally stable and mature enough to cope with the many possible outcomes (good and bad), make the decision like a grown up. Deciding not to search is a reasonable choice for many folks.

How do I contact my newly discovered blood relatives ? Use care and diplomacy and don't assume that you know the whole situation or what they may think or know about the adoption situation. If possible contact birth parents before siblings.  Think of all the possible reactions you might get of you sent a txt "Hi am your long lost brother." and don't do it that way.  Starting out with a "Can we talk about some mutual family history that has been discovered around the date xxxxxxxx. ? " is a better way. This is delicate, you don't have to do it yourself, ask a trained family councillor to assist.

What relationship can I expect with my birth relatives ?  Ask first "How well do you get along with current friends and family ?"  Building relationships is about mutual support and investment of time and effort. A genetic relationship does not change that. Over time, with long periods of no contact, perceptions and memories of events and motivations for those events can change.

When shall I tell my child they are adopted or have difference birth parents than us ?
From my story at adoption time my Mum asked "When would be a good time to tell the kids that they are adopted ? ” The Nurse in charge of adoptions said “Take them home, put them on your knee, tell them they were adopted and how special that makes them.” This works both ways by normalising the story and removing the need for a big reveal at what can be a difficult time. Retelling the story helps child and Mums & Dads to normalise the story.

Warning : This area is fraught with emotional potholes and historical welfare issues:
Contrast this :

The Salvation Army (Canada) says it is conducting an internal review into its historic maternity homes, just as a retired Calgary judge — who was once a high-ranking child welfare worker in the city — has come forward and corroborated some of the claims mothers have recently made about coercive adoption practices directed at unmarried mothers decades ago.   from National Post of Canada

with this kind offer

The Family Tracing Service is here to support people who are looking for family members. It is never too late to find a loved one, so get in contact with us and we can help you with your search. From Salvation Army UK website

attitudes and behaviours of both people and organisation change over time.


Adoption Story Part 1 - Discovery
Adoption Story Part 2 - Reunion
Adoption Story Part 3 - Lessons

Adoption Story - Reunion after 57 years. 2/2

Reflections on 28 Feb 2018 a week after the trip.

So how did the trip go ?

Amazingly well. It was a bit of a whirlwind tour meeting birth mum (Mauri), aunt and niece along with seven out of the eight brothers and sisters.  

How did the Journey go ?

Landing first in Las Vegas we were met with big hugs from Mauri and sister Krystal. Within a day we had also met sister Norah and Sarah P and Aunt Sarah. First night we did the Las Vegas thing, eating at a large Casino resort buffet. Sister Norah then took Alice and I out to the Valley of Fire state park to see the stunning scenery.  We also visited the Las Vegas mob Museum but did not find any more of our family there. Family dinner at Sarah Ps house topped off the day.

A short flight took us to a windy and cold San Francisco, where just north of the city we met with brother Jeremy and Paul at their tie-dye clothing businesses work place. Jamminon.com   We tried our hands at making our own tie-dye which seemed to come out great and certainly takes more skill and technique than I imagined. Dinner that evening at the brothers house helped explore their Californian life style.

Next day a short road trip took us to Sacramento to meet with oldest sister Kim, husband Mike and nephew Derek. They had they had kindly put us up in a local hotel overnight and we all went out to a hearty dinner at the Roadhouse. {I knew we would get on as soon as I saw the DVD of Serenity & Firefly on the shelf.}  We did get on really well, Alice having a lot in common with Kim who runs a mineral powder make up business.

The next day saw us whizzing to the airport just in time for a flight to the furthest stop on the tour, Tucson.  Unfortunately darling daughter managed to pick up a cold and it was unusually raining in Tucson. At this point we had to change the tour motto from “The British are coming.” to “The British weather is coming”.  Brother Josh and Sally were very hospitable and looked after us over a couple of nights. Josh and I got out for mountain bike ride and after dinner drinks in town with friends to watch the Arizona local derby basketball match at a downtown bar.  A visit to a large aircraft museum on the way back to the airport filled in the last morning.  Josh and I have the most in common career wise as he runs a large software technology business Pagely.com  

The short flight from Tucson took us back to Las Vegas. The next day was “The Dam Dog day” where we went to see sister Norah run her agility dog Cider followed by a trip to Hover dam with Krystal.  Coincidently Daughter Alice has been doing dog agility with her poodle Mr. Biggles for the last couple of years.  A visit to the Las Vegas strip with Krystal gave us the inside stories behind the sparkles. The evening topped off seeing the fabulous Cirque du Soleil Beatles show "Love" at Majestic casino.

There was a difficult decision on the penultimate day - go shopping with Alice and the sisters or drive out to the nearby Blue Diamond town and hire a mountain bike and ride off into the desert.  That decision took less than a nano-second.  Instead of huffing and puffing like a stranded whale outside the shops waiting for the girls to appear, I huffed and puffed up the desert hills.  After a quick dinner later that evening we all went to see “Black Panther” at one of the larger Las Vegas cinemas. 

The final day was packing and getting to the airport for the return journey. The family was so welcoming and generous that, despite offloading loads of Early Grey tea, Marmite and Lint chocolate Bunnies, we needed an extra suitcase on the return trip that brought us back to Newquay on a cold February morning. 

Reflections

That Google search was one from where there was no return and our family landscape has really changed for the better.  { This certainly is the family extension jackpot. }  I have some wicked new tie-dye clothes and a couple of business ideas to develop. Meeting Birth Mum Mauri and all those brother and sisters & aunt was a great adventure that because of their friendliness completely exceeded all we could hope for.  They have promised return visits but hopefully not all arriving at once.

From a technology point of view - if folks don't feel comfortable to post detailed blogs and pages magic search results like this won't happen. 

Listen to more on BBC Radio 4 - Saturday Live 10 March 2018


Adoption Story Part 1 - Discovery
Adoption Story Part 2 - Reunion
Adoption Story Part 3 - Lessons

Adoption Story - Reunion after 57 years. 1/3

With Jayne, the sister, that I grew up with.

In early February 2018, my daughter, and I traveled to the USA to meet our recently discovered, extended family. This is the story.

57 years ago I was adopted by my mum and dad, Norman and Lily “Pat". Adoption was never a big thing as I’ve always known my sister and I were adopted. There had been no surprises in that area. At adoption time Mum asked "When would be a good time to tell the kids that they are adopted ? ” The Nurse in charge of adoptions said “Take them home, put them on your knee, tell them they were adopted and how special that makes them.”  I was chosen by mum and dad and brought up by them as their very own child.  { Retelling helps mum and dad to normalise the story. }

I have since learned that my birth mother only knew two things about my adoption, besides it being the very last thing in the world that she wanted.  The parents adopting her son had adopted a little girl a couple of years before me, and they were being allowed to adopt another child. To her that meant they were doing a good job and likely to give her son a good home where she could not.  When she waited in the Adoption office for the Sister in charge to take her son to his new parents, there was a file laying open on the desk.  The name on the file was my surname.  She filed it away as a piece of disconnected information. Over the years she held the hope in her heart that, eventually, her son would look for her...and, just in case he did, she had scattered a few electronic breadcrumbs for him to find...and kept her own birth name. As she had lived in Canada and the USA since I was born, she says reunion was rather a forlorn hope...

I had never been particularly curious about my genetic background but these days, in medical terms, genetic heritage is very important. A few years ago my big sister Jayne, took several months through official channels to discover her birth mum.  With further prompting from daughter Alice and darling wife Jenny, with a fresh mug of coffee, I embarked on my family research. The starting paperwork was the court adoption certificate that showed my original name, place and date of birth, along with my post adoption name. I put my original name, date and place of birth into Google, hit 'return' and immediately found what appeared be my birth family.  Using the official route of £10 via the UK passport office to obtain my pre-adoption birth certificate confirmed the research, and provided my birth mother's name.   { Between Tuesday 10:00 and 10:10, coffee still warm, my whole familly landscape changed. }

The Google search had turned up my birth mum's website, with a page she had set up prior to going to  work in Saudi Arabia for 6 months in Spring 2011, thinking it was easier to point people to the page, rather than to try to explain her rather large, extended family.  The page listed my birth mum's other children and my aunts and my nieces and nephews. The siblings all had their numbers with their names... "2", "3", etc.  This was going to be a big family extension.

The blog was so touching, included with the list of her children was an entry describing how her first born had been adopted away at 3 months. Right there was the matching birth name, place and date. And I was listed as “1”.  Making contact with long lost relatives can be a delicate occasion, but the blog entries reassured me that there was no secrecy around the adopted child { in that family}. 

Reaching out via email eventually led to "friending" my birth mum on Facebook and then to Messenger contact with her and the rest of her side of the family.  Over the next few weeks, lots of email and pictures were exchanged. Turns out I have a lot of family in the USA southwest: 3 sisters in Las Vegas, Nevada, and one in Sacramento, CA, and 3 brothers in San Francisco, CA and one in Tucson, Arizona as well as two aunts and 10 nieces and nephews...and a whole lot of new Facebook friends.

February 2018 visit to the USA will be the family reunions 57 years in the making. Getting to meet my new, extended family is going to be a big, exciting journey. Facebook may show someone's activities, but only meeting in real life can allow you to get to know them 'up close and personal’. 

Journalists will always ask “.. and how does that make you feel ?”  For Mauri (my birth mum), she tells me this is a joyous, life-changing event that resolves a long-standing area of loss and uncertainty. For me, it’s a new family thing to which I am adjusting.  Soon Alice and I will visit everyone.  It’s going to be emotional; it’s going to be fun; and it’s not going to be like any other journey, ever ! 


Adoption Story Part 1 - Discovery
Adoption Story Part 2 - Reunion
Adoption Story Part 3 - Lessons