All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 Tautonymic number counting (Posted on 2022-09-04)
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?

 See The Solution Submitted by K Sengupta Rating: 5.0000 (1 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
 solution (parts 2 and 3) | Comment 1 of 2
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

 Search: Search body:
Forums (0)