Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

Thread Subject:
PE help

Subject: PE help

From: proecsm

Date: 9 Nov, 2010 01:23:04

Message: 1 of 6

I am working on Project Euler # 55 and have code that give a 'tantilizingly' close answer to the generally accepted answer. It matches the first 45 terms given in OEIS, but am wondering if I am missing something from the int2str conversions or precision issues. I am only missing a few terms...

<pre>
for n = 100:10000
    snum = int2str(n);
    c = 0;
    while ~all(snum-fliplr(snum)==0)
        
        c=c+1;
        snum = int2str(str2double(snum)+str2double(fliplr(snum)));
        
        if c > 50
            lychrel = [lychrel n]; %#ok<*AGROW>
            break
        end
    end
end
<\pre>

Subject: PE help

From: Roger Stafford

Date: 9 Nov, 2010 02:05:05

Message: 2 of 6

"proecsm " <proecsm@gmail.com> wrote in message <iba7po$kd0$1@fred.mathworks.com>...
> I am working on Project Euler # 55 and have code that give a 'tantilizingly' close answer to the generally accepted answer. It matches the first 45 terms given in OEIS, but am wondering if I am missing something from the int2str conversions or precision issues. I am only missing a few terms...
>
> <pre>
> for n = 100:10000
> snum = int2str(n);
> c = 0;
> while ~all(snum-fliplr(snum)==0)
>
> c=c+1;
> snum = int2str(str2double(snum)+str2double(fliplr(snum)));
>
> if c > 50
> lychrel = [lychrel n]; %#ok<*AGROW>
> break
> end
> end
> end
> <\pre>
- - - - - - - - - -
  If you multiply 10000 * 2^50, that gives a number in the neighborhood of 1e19, and that lies beyond the range of integers that double can represent exactly. You may have thought some of the numbers were not lychrel because of round off errors.

Roger Stafford

Subject: PE help

From: proecsm

Date: 9 Nov, 2010 02:34:04

Message: 3 of 6

"Roger Stafford" <ellieandrogerxyzzy@mindspring.com.invalid> wrote in message <ibaa8h$q5b$1@fred.mathworks.com>...
> "proecsm " <proecsm@gmail.com> wrote in message <iba7po$kd0$1@fred.mathworks.com>...
> > I am working on Project Euler # 55 and have code that give a 'tantilizingly' close answer to the generally accepted answer. It matches the first 45 terms given in OEIS, but am wondering if I am missing something from the int2str conversions or precision issues. I am only missing a few terms...
> >
> > <pre>
> > for n = 100:10000
> > snum = int2str(n);
> > c = 0;
> > while ~all(snum-fliplr(snum)==0)
> >
> > c=c+1;
> > snum = int2str(str2double(snum)+str2double(fliplr(snum)));
> >
> > if c > 50
> > lychrel = [lychrel n]; %#ok<*AGROW>
> > break
> > end
> > end
> > end
> > <\pre>
> - - - - - - - - - -
> If you multiply 10000 * 2^50, that gives a number in the neighborhood of 1e19, and that lies beyond the range of integers that double can represent exactly. You may have thought some of the numbers were not lychrel because of round off errors.
>
> Roger Stafford

Thanks Roger, I will investigate using the symbolic toolbox or maple :( If anyone knows of a longer list of (potential) lychrel numbers that I can compare my results to, I'd be interested. I suspect they would be at the upper end of the range, however the number 89 (which I used for debug purposes) defies that assumption...

thanks for the help

Subject: PE help

From: Roger Stafford

Date: 9 Nov, 2010 03:57:03

Message: 4 of 6

"proecsm " <proecsm@gmail.com> wrote in message <ibabus$eg6$1@fred.mathworks.com>...
> "Roger Stafford" <ellieandrogerxyzzy@mindspring.com.invalid> wrote in message <ibaa8h$q5b$1@fred.mathworks.com>...
> > "proecsm " <proecsm@gmail.com> wrote in message <iba7po$kd0$1@fred.mathworks.com>...
> > > I am working on Project Euler # 55 and have code that give a 'tantilizingly' close answer to the generally accepted answer. It matches the first 45 terms given in OEIS, but am wondering if I am missing something from the int2str conversions or precision issues. I am only missing a few terms...
> > >
> > > <pre>
> > > for n = 100:10000
> > > snum = int2str(n);
> > > c = 0;
> > > while ~all(snum-fliplr(snum)==0)
> > >
> > > c=c+1;
> > > snum = int2str(str2double(snum)+str2double(fliplr(snum)));
> > >
> > > if c > 50
> > > lychrel = [lychrel n]; %#ok<*AGROW>
> > > break
> > > end
> > > end
> > > end
> > > <\pre>
> > - - - - - - - - - -
> > If you multiply 10000 * 2^50, that gives a number in the neighborhood of 1e19, and that lies beyond the range of integers that double can represent exactly. You may have thought some of the numbers were not lychrel because of round off errors.
> >
> > Roger Stafford
>
> Thanks Roger, I will investigate using the symbolic toolbox or maple :( If anyone knows of a longer list of (potential) lychrel numbers that I can compare my results to, I'd be interested. I suspect they would be at the upper end of the range, however the number 89 (which I used for debug purposes) defies that assumption...
>
> thanks for the help
- - - - - - - - - -
  One other observation. I think you would miss the lychrel number 4774 and other palindromes like it because you compare a number with its reversed form before having performed the first step in addition. You need to ensure that your while-loop takes at least one step before exiting.

Roger Stafford

Subject: PE help

From: proecsm

Date: 9 Nov, 2010 23:09:04

Message: 5 of 6

"Roger Stafford" <ellieandrogerxyzzy@mindspring.com.invalid> wrote in message <ibagqf$muk$1@fred.mathworks.com>...
> "proecsm " <proecsm@gmail.com> wrote in message <ibabus$eg6$1@fred.mathworks.com>...
> > "Roger Stafford" <ellieandrogerxyzzy@mindspring.com.invalid> wrote in message <ibaa8h$q5b$1@fred.mathworks.com>...
> > > "proecsm " <proecsm@gmail.com> wrote in message <iba7po$kd0$1@fred.mathworks.com>...
> > > > I am working on Project Euler # 55 and have code that give a 'tantilizingly' close answer to the generally accepted answer. It matches the first 45 terms given in OEIS, but am wondering if I am missing something from the int2str conversions or precision issues. I am only missing a few terms...
> > > >
> > > > <pre>
> > > > for n = 100:10000
> > > > snum = int2str(n);
> > > > c = 0;
> > > > while ~all(snum-fliplr(snum)==0)
> > > >
> > > > c=c+1;
> > > > snum = int2str(str2double(snum)+str2double(fliplr(snum)));
> > > >
> > > > if c > 50
> > > > lychrel = [lychrel n]; %#ok<*AGROW>
> > > > break
> > > > end
> > > > end
> > > > end
> > > > <\pre>
> > > - - - - - - - - - -
> > > If you multiply 10000 * 2^50, that gives a number in the neighborhood of 1e19, and that lies beyond the range of integers that double can represent exactly. You may have thought some of the numbers were not lychrel because of round off errors.
> > >
> > > Roger Stafford
> >
> > Thanks Roger, I will investigate using the symbolic toolbox or maple :( If anyone knows of a longer list of (potential) lychrel numbers that I can compare my results to, I'd be interested. I suspect they would be at the upper end of the range, however the number 89 (which I used for debug purposes) defies that assumption...
> >
> > thanks for the help
> - - - - - - - - - -
> One other observation. I think you would miss the lychrel number 4774 and other palindromes like it because you compare a number with its reversed form before having performed the first step in addition. You need to ensure that your while-loop takes at least one step before exiting.
>
> Roger Stafford

Actually, after fixing the while loop problem I get the right answer. To make the code more robust, I should rewrite it to account for round off. I also discovered this http://blogs.mathworks.com/loren/2009/04/06/palindrome-numbers/

thanks for the help

Subject: PE help

From: Roger Stafford

Date: 10 Nov, 2010 01:41:03

Message: 6 of 6

"proecsm " <proecsm@gmail.com> wrote in message <ibckag$r57$1@fred.mathworks.com>...
> Actually, after fixing the while loop problem I get the right answer. To make the code more robust, I should rewrite it to account for round off. I also discovered this http://blogs.mathworks.com/loren/2009/04/06/palindrome-numbers/
>
> thanks for the help
- - - - - - - - - - -
  Bear in mind that the double floating point format can accurately represent all the non-negative integers from 0 up to 2^53 = 9007199254740992. No rounding will occur for these integers. Beyond that value rounding becomes necessary because the format cannot represent all the integers. For example 2^53+1 can't be represented because there aren't enough available bits to store it, so it would have to be rounded to either 2^53 or 2^53+2.

  Yesterday I used your code to test the known candidate lychrel nunber 196. Long before it reached the c-count of 50 the sum had far exceeded 2^53 which meant that all further testing was rendered meaningless. Palindromes could look like non-palindromes and non-palindromes could look like palindromes.

  Therefore beyond that crucial point the numbers must be represented in an altered form. Perhaps make each element of a (uint8 ?) array a numerical decimal digit and do decimal addition with it. (Any digit that exceeds 9 would have 10 subtracted with a carry of 1 brought to the next digit.) The addition would of course be slower but it wouldn't be necessary to continually convert between decimal and binary at each step, and reversing the digit order would only be a matter of proper indexing. You needn't produce a separate reversed copy for testing or addition. All of this is approximately what the Symbolic Toolbox would have to do, though perhaps in a less straightforward manner.

Roger Stafford

Tags for this Thread

What are tags?

A tag is like a keyword or category label associated with each thread. Tags make it easier for you to find threads of interest.

Anyone can tag a thread. Tags are public and visible to everyone.

Contact us