Home > Numbers
| Evened N and 3N Extended (Posted on 2023-07-29) |
 |
N is a number with the property that all its digits are even.
3N also has that property.
Example: N=208 and 3N=624.
How many possible values of N have 22 digits? (3N may have 22 or 23 digits.)
For reference: Evened N and 3N is a version of this problem where N is only a 3 digit number.
|
|
Submitted by Brian Smith
|
|
No Rating
|
|
|
Solution:
|
(Hide)
|
I'll start by analyzing individual digits.
If there is a carry in the multiplication of 3 times N, then that carry needs to be a 2 so that the next digit remains even.
If a digit in N is 0 then it will be either 3*0=0 or 3*0+2=2. So 0 can occur anywhere in N.
If a digit in N is 2 then it will be either 3*2=6 or 3*2+2=8. So 2 can occur anywhere in N.
If a digit in N is 4 then it will be either 3*4=12 or 3*4+2=14. Both have a carry of 1, so 4 cannot occur in N.
If a digit in N is 8 then it will be either 3*8=24 or 3*8+2=26. Both have a carry of 2, so 8 can occur anywhere in N.
If a digit in N is 6 then it will be either 3*6=18 or 3*6+2=20. The first case has a carry of 1, but the second case has a carry of 2. Then for 6 to appear in N it must be followed by another 6 or an 8.
Putting these together we can create a set of building blocks for possible N. Single digits 0, 2, and 8, and multi-digit blocks consisting of a string of 6's terminated with an 8 (68, 668, 6668, etc).
So then we can build possible N recursively. For a length D value of N, it can be made by appending a 0, 2, or 8 to a length D-1 value of N; appending 68 to a length D-2 value of N; .... all the way down to appending a length D-1 string of 666...6668(D-2 6's) to a length 1 value of N, or finally creating a whole new N out of D-1 6's and an 8.
Define f(D) to be the number of values of N if length D. Then the recursive construction implies the formula f(D) = 3*f(D-1) + f(D-2) + f(D-3) + ... + f(1) + 1.
We can simplify this by calculating f(D) - f(D-1)
= [3*f(D-1) + f(D-2) + f(D-3) + ... + f(1) + 1] - [3*f(D-2) + f(D-3) + ... + f(1) + 1]
= 3*f(D-1) - 2*f(D-2)
Then f(D) = 4*f(D-1) - 2*f(D-2)
f(1)=2 from N = {2,8} and f(2)=7 from N = {20,22,28,68,80,82,88}.
Then the sequence for f(D) can be easily calculated as 2, 7, 24, 82, 280, 956, 3264, 11144, 38048, 129904, 443520, 1514272, 5170048, 17651648, 60266496, 205762688, 702517760, 2398545664, 8189147136, 27959497216, 95459694592, 325919783936, ....
There are 325919783936 possible values of 22 digit length N such that N and 3N have with the property that all its digits are even. |
Comments: (
You must be logged in to post comments.)
|
|
Please log in:
Forums (1)
Newest Problems
Random Problem
FAQ |
About This Site
Site Statistics
New Comments (6)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On
Chatterbox:
|
