Suppose you want to know how many
tautonymic numbers are in the set of integers from 1 to N.
- Can you provide a formula for this?
- Otherwise, can you devise an algorithm, as efficient as possible, to find the answer?
- Are there special values of N for which there is a simple formula?
The definition of a tautonymic number is a little bit redundant:
A tautonymic number is one which can be divided into two equal non-palindromic halves, with each part having at least two different digits.
Well, if each part had only identical digits it would be a palindrome anyway, so:
A tautonymic number is one which can be divided into two equal non-palindromic halves.
It also necessarily has an even number of digits, and the left half determines what the right half is.
If N has an odd number of digits, say n, the cardinality of the set under discussion is that of the highest number with n-1 digits.
If N has an even number of digits the number of tautonomic numbers less than N if the number of numbers less than the number that constitutes the left half of N minus the number that are palindromes. OEIS A070199 contains an algorithm for the number of palindromes of length <=n. Unfortunately it doesn't work for ordinary cutoff points like "the number of palindromes under 675".
So a special case would be where N is 10^(2*k)-1 where k>1.
What is sought is the cardinality of numbers with half as many digits as N minus the number of palindromes. Repeat this for the next lower such even-length and add that in.
The cardinality of k-digit numbers (half the length of N) and lower is 10^k. But we can subtract 10 for the first 10: zero through 9.
The number of palindromes of length n (our k) or lower is
(-2*sqrt(10)+10^(n/2)*(11+2*sqrt(10)+(-1)^n*(-11+2*sqrt(10))))/(2*sqrt(10))
per A070199 (formula verified against list shown there; the list also shows zero is included in the count).
Since the count of 10 for the single-digit number is included in both formulae, they cancel in the subtraction.
10^k - (-2*sqrt(10)+10^(k/2)*(11+2*sqrt(10)+(-1)^k*(-11+2*sqrt(10))))/(2*sqrt(10))
where k is half the length of N.
The program following calculates the number of numbers and the number of palindromes separately and subtracts them, and then uses the formula as a whole to show the results:
clc
digits 200
for k=2:7
N=10^(2*k)-1;
cNum=10^k;
allTheNumbers=cNum-10; % exclude the single-digit nos.
allThePals=pal(k)-10; % exclude the single-digit nos.
disp([N allTheNumbers-allThePals])
disp([N 10^k - (-2*sqrt(10)+10^(k/2)*(11+2*sqrt(10)+(-1)^k*(-11+2*sqrt(10))))/(2*sqrt(10))])
end
function p=pal(n0)
n=vpa(n0);
p=(-2*sqrt(vpa(10))+10^(n/2)*(11+2*sqrt(vpa(10))+(-1)^n*(-11+2*sqrt(vpa(10)))))/(2*sqrt(vpa(10)));
end
The output:
[9999, 81.0]
9999 81
[999999, 891.0]
999999 891
[99999999, 9801.0]
99999999 9801
[9999999999, 98901.0]
9999999999 98901
[999999999999, 998001.0]
999999999999 998001
[99999999999999, 9989001.0]
99999999999999 9989001
Formatted nicely:
N tautonyms under N
9999 81
999999 891
99999999 9801
9999999999 98901
999999999999 998001
99999999999999 9989001
This covers part three, special values of N where there's a somewhat simple formula. Now for part two, a general algorithm.
for limit=[375889 9999 99999999 9999999999 999999999999]
mxsz=floor(length(char(string(limit)))/2);
mxnum=str2num(repmat('9',1,mxsz));
ct=0;
for hnum=10:mxnum
hns=char(string(hnum));
ns=[hns hns];
if str2num(ns)>limit
break
end
if ~ispal(ns)
ct=ct+1;
end
end
disp([limit ct])
end
function ip=ispal(ns)
ip=true;
for i=1:floor(length(ns)/2)
if ns(i)~=ns(length(ns)+1-i)
ip=false;
end
end
end
finds
N number of tautonyms
375889 329
9999 81
99999999 9801
9999999999 98901
999999999999 998001
verifying the special formula as well as showing a value for a generalized N.
|
|
Posted by Charlie
on 2022-09-04 10:04:04 |
solution (parts 2 and 3)
