Finding Happy 6-Digit Numbers/Strings

[T@P]

a number is happy if the sum of the first three digits equals the sum of the last three digits.

how many 6 digit happy numbers are there?

a slightly easier but very similar question how mnay happy 6 number strings are there? (in case you don't see the difference, a number cannot start with 0, while a 6 digit "string" can.)

 

[Bartholomew]

So how many ways are there to form each number 0 to 27 by adding three digits? I tried from 0 to 3 and got 1, 3, 6, and 10 respectively. I assume that this pattern of adding 2, 3, 4, will continue adding 5, 6, etc. up to number 13 (which I get 105 for), and then 14 is 105, and then decrease down to 27 since it is symmetrical. This assumption may be wrong but working on it, I wrote the number of ways to form each number 0 to 27. Then I squared each of them and added all the squares together. Result (for the string which can start with 0): 69326

Edit: To find it for the numbers which can't start with 0, you first find the ways to form each possible sum of 2 digits. For sums 0, 1, 2, 3, I got 1, 2, 3, 4 ways respectively. Again assuming the pattern continues (and is symmetrical, reaching a peak at 9), I multiplied each way (0 to 18) to get by the corresponding number of ways to get the same sum with 3 digits, and added all of those products together. I got 5500 though there is a greater chance of error here. 69326 - 5500 = 63826

Edit: (changed color)

 

[Rogerio]

how many 6 digit happy numbers are there?
how mnay happy 6 number strings are there?

There are
50412 happy numbers and 55252 happy strings.

 

[Bartholomew]

How did you get that answer rogerio?

 

[Gokul43201]

I agree with Rogerio...with one small difference : I would quote the number of happy strings first, and then the happy numbers. I'd be surprised if he actually solved it the other way.

Bart, your first error is in assuming the trend 1,3,6,10,15,... continues all the way to the mid-point (ie : for sum = 13). This works up to 55 (at sum = 9), but from there, the differences start to fall off, because you can't put the numbers 10, 11,... into a single digit. So, while in the previous cases, the smallest number for sum=N was represented by 00N, this will not be true anymore for sum=10 (and here the smallest number is 019). So, while the differences increased by 1 each time, up to a value of 10 for sum=9, they will start to fall off by 2 for the next 4 numbers, giving 63, 69, 73 and 75.

Twice the sum of the squares of these numbers is the number of happy strings.

Now, for the numbers beginning with a 0 : your mistake was in assuming that this peaks at 9. It will actually peak at 10. For sum=9, you have 009, 090, 018, 081, 027, 072, 063, 036, 054, 045 (clearly 10 numbers). Multiplying each of these with the corresponding numbers of ways of getting each sum, gives <4840[/color]>.

Number of happy strings - <4840[/color]> = number of happy numbers.

 

[Bartholomew]

Gokul, my first error (forgetting about no digits after 9) was the only one I made. The other you described I did not make. How do you know that the correction is that they fall off by 2 though?

 

[Gokul43201]

Gokul, my first error (forgetting about no digits after 9) was the only one I made. The other you described I did not make.

Sorry about that

How do you know that the correction is that they fall off by 2 though?

Umm...I'm a little embarrassed to say this but I actually wrote down all the possibilities from 10 to 13 and counted them. It's really easier and quicker than it seems. Once you develop a rhythm, you can do each number in about a minute.

Let me demonstrate :

For sum=10 you have,

055,064,073,082,091,154,163,172,181,244,253,262,343 (notice the pattern)

Each number with a repeating digit has 3 arrangements and numbers without repetition have 6 arrangements. There are 5 of the former and 8 of the latter, so that's 8*6 + 5*3 = 63.

 

[Bartholomew]

That's one way, and probably faster than finding the formula (though probably slower than writing a program to check each number from 100000 to 999999).

Anyway, I thought about it and now know why the number of ways are as they are. To determine how many ways there are to write a number abc so that a + b + c = some sum n, you look at it as a distribution of n objects into containers a, b, and c. So that's C(n + 2, 2), which reduces to (n + 2)(n + 1)/2. Once the number of ways starts being limited by the maximum of 9 in each "container," you look at the overflow and subtract it out. So for 10, any arrangement of 10, 0, and 0 is excluded, and for 11, any arrangement of 11, 0, 0, or of 10, 1, 0 is excluded. Write those three triplets (10, 0, 0), (10 + 1, 0, 0), (10, 1, 0). So for n > 9, you are depositing (n - 10) 1's, and then one 10, into three containers to form the excluded ways. So that's C(n - 10 + 2, 2) * 3, which for n > 9 reduces to (n - 8)(n - 9) / 2 * 3, so the expression for the number of ways for 9 < n <= (the midpoint) is (n + 2)(n + 1)/2 - (n - 8)(n - 9) / 2 * 3.

 

[T@P]

thanks a lot people