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

Home > Algorithms
Tautonymic number counting (Posted on 2022-09-04) Difficulty: 3 of 5
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 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
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (1)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2024 by Animus Pactum Consulting. All rights reserved. Privacy Information