Tough Problem 1

[barry houdini]

Hello Fairwinds,<?xml:namespace prefix = o ns = "urn:schemas-microsoft-comfficeffice" /><o></o>
<o> </o>
Now that’s what I call a formula, I’ll need to go away and work out exactly how it works.<o></o>
<o> </o>
It prompted me to look again at my suggestion. I had realised that I could limit the MOD divisor range to the square root of N but that didn’t work within my original formula because my “primeness” test for each n of 1 to N was that it would have a single factor (not including 1), i.e. n itself. If I restricted it to SQRT(N) then some primes (those < SQRT(N)) would have no factors, and the others would have 1.<o></o>
<o> </o>
But I can change the formula slightly to take that into account (calculating whether each number needs 1 factor or 0 to be prime).<o></o>
<o> </o>
Having made that fix I realised that MMULT was still limiting the value of N to 5465 (although that restriction doesn’t apply in Excel 2007) so I changed the formula further to only consider odd numbers.<o></o>
<o> </o>
This formula, then, works on values of N up to 10926 (shouldn’t be a problem to go higher in Excel 2007 but I can’t access that version right now).

=SUM((FREQUENCY(ROW(INDIRECT("1:"&INT(A1/2+1.5)))*2+1,(MMULT((MOD(ROW(INDIRECT("2:"&INT(A1/2-0.5)))*2+1,TRANSPOSE(ROW(INDIRECT("2:"&INT(A1^(1/2))))))=0)+0,ROW(INDIRECT("2:"&INT(A1^(1/2))))^0)=(ROW(INDIRECT("2:"&INT(A1/2-0.5)))*2+1<=INT(A1^(1/2)))+0)*ROW(INDIRECT("2:"&INT(A1/2-0.5)))*2+1)=1)+0)

confirmed with CTRL+SHIFT+ENTER<o></o>

 

[barry houdini]

.........Update.......

I used that last formula in Excel 2007 to calculate when N = 100,000 [the result was 1223] but any higher and I got some "out of resources" errors.

 

[pgc01]

Hi sous2817

Thanks for posting the formulas. THey seem to work ok, except for the 1 that, as Andrew already said, is not a prime. The second formula seems more efficient as only divisors up to the the square root of the dividend.

 

[pgc01]

Hi Fairwinds, Barry

I tried both solutions and they they both work ok, and both are great solutions!!! Barry's solution is more compact and faster to calculate.


I'll post my formula now:

=SUM(--(MMULT(--((3+2*ROW(INDIRECT("1:"&INT((A1-3)/2)))=TRANSPOSE(3+2*ROW(INDIRECT("1:"&INT((A1-3)/2)))))+(3+2*ROW(INDIRECT("1:"&INT((A1-3)/2)))=TRANSPOSE(3+2*ROW(INDIRECT("1:"&INT((A1-3)/2))))-2)),--(MMULT(1-(MOD(3+2*ROW(INDIRECT("1:"&INT((A1-3)/2))),TRANSPOSE(1+2*ROW(INDIRECT("1:"&ROUNDUP(A1^0.5/2,0)))))<>0)-(3+2*ROW(INDIRECT("1:"&INT((A1-3)/2)))=TRANSPOSE(1+2*ROW(INDIRECT("1:"&ROUNDUP(A1^0.5/2,0))))),--(1+2*ROW(INDIRECT("1:"&ROUNDUP(A1^0.5/2,0)))>0))=0))=2))

Both Fairwinds' and Barry's solutions are more efficient, faster and more compact than mine. I didn't use Frequency() and I guess that that's one of the reasons for my formula being slower. A strange thing that happened: I was working in excel 2000, to be sure that the solution would be compatible with versions before the excel 2007. When the solution was working in excel 2000, I tried it in excel 2007 and it only calculated until about 9500, then it says it's out of resouces!!! So, somehow the excel 2000 manages to be more efficient in the memory management than excel 2007??


I think we already have good solutions for this problem. I'll start thinking about the next one.

I think we got a very week participation in this problems and I think the reason was the difficulty of the problem. Although I did want these problems to be a challenge I should have posted as a first problem a simpler one. I'll try one more time, both a formula and a vba problems, and try to choose better the problems so that there's more discussion and participation.

Cheers

 

[barry houdini]

Hello pgc,

Thanks for your comments. I thought it was an excellent challenge but, as you say, perhaps a little complex for mass participation.

If you are going to try more (and I think you should - if you run out of ideas I might have some of my own) then I suggest that you vary the level of difficulty, perhaps an easier one now followed by a more difficult one after?

 

[pgc01]

Hello pgc,

Thanks for your comments. I thought it was an excellent challenge but, as you say, perhaps a little complex for mass participation.

If you are going to try more (and I think you should - if you run out of ideas I might have some of my own) then I suggest that you vary the level of difficulty, perhaps an easier one now followed by a more difficult one after?

Thank you Barry. That's a good idea, to alternate the difficulty of the problems, and I'm sure I'll take you up on your offer.

Cheers