Discussion about math, puzzles, games and fun. Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ π -¹ ² ³ °

You are not logged in.

- Topics: Active | Unanswered

**krassi_holmz****Real Member**- Registered: 2005-12-02
- Posts: 1,905

int x is a perfect power iff there exists int a and int b for which

For example, 4 and 8 are perfect powers, but 10 isn't.

The function

gives the n-th perfect square.

etc.

The sequence

is very interesting. I'll post some properties of it.

IPBLE: Increasing Performance By Lowering Expectations.

Offline

**krassi_holmz****Real Member**- Registered: 2005-12-02
- Posts: 1,905

First, a program. (C++ )

```
#include<iostream>
#include<fstream>
#include<math.h>
using namespace std;
const long int n=1000000;
int main(){
//making the array
cout<<"n = "<<n<<endl;
bool result[n];
for(long int i=1;i<n;i++){
result[i]=false;
}
for(long int i=2;i<=sqrt((double)n)+1;i++){
if(!result[i-1]){
long int pw=i*i;
while(pw<=n){
result[pw-1]=true;
pw*=i;
}
}
}
ofstream file("results.txt",ios::out);
for(long int i=0;i<n;i++){
if(result[i]){
file<<i+1<<",";
}
}
cout<<"For results, see 'results.txt'. Press any key to quit:";
char c;
cin>>c;
return c;
}
```

This is some kind of Erastrotenes prime sieve.

But there's some bug: for n=1000000 (milion) it works fine, but somewhere between 1010000 and 11000000 it starts to give some overflow error.

IPBLE: Increasing Performance By Lowering Expectations.

Offline

**krassi_holmz****Real Member**- Registered: 2005-12-02
- Posts: 1,905

Here's S up to i=1000000(milion):

```
1,4,8,9,16,25,27,32,36,49,64,81,100,121,125,128,144,169,
196,216,225,243,256,289,324,343,361,400,441,484,512,529,
576,625,676,729,784,841,900,961,1000,1024,1089,1156,1225,
1296,1331,1369,1444,1521,1600,1681,1728,1764,1849,1936,
2025,2048,2116,2187,2197,2209,2304,2401,2500,2601,2704,
2744,2809,2916,3025,3125,3136,3249,3364,3375,3481,3600,
3721,3844,3969,4096,4225,4356,4489,4624,4761,4900,4913,
5041,5184,5329,5476,5625,5776,5832,5929,6084,6241,6400,
6561,6724,6859,6889,7056,7225,7396,7569,7744,7776,7921,
8000,8100,8192,8281,8464,8649,8836,9025,9216,9261,9409,
9604,9801,10000,10201,10404,10609,10648,10816,11025,11236,
11449,11664,11881,12100,12167,12321,12544,12769,12996,13225,
13456,13689,13824,13924,14161,14400,14641,14884,15129,15376,
15625,15876,16129,16384,16641,16807,16900,17161,17424,17576,
17689,17956,18225,18496,18769,19044,19321,19600,19683,19881,
20164,20449,20736,21025,21316,21609,21904,21952,22201,22500,
22801,23104,23409,23716,24025,24336,24389,24649,24964,25281,
25600,25921,26244,26569,26896,27000,27225,27556,27889,28224,
28561,28900,29241,29584,29791,29929,30276,30625,30976,31329,
31684,32041,32400,32761,32768,33124,33489,33856,34225,34596,
34969,35344,35721,35937,36100,36481,36864,37249,37636,38025,
38416,38809,39204,39304,39601,40000,40401,40804,41209,41616,
42025,42436,42849,42875,43264,43681,44100,44521,44944,45369,
45796,46225,46656,47089,47524,47961,48400,48841,49284,49729,
50176,50625,50653,51076,51529,51984,52441,52900,53361,53824,
54289,54756,54872,55225,55696,56169,56644,57121,57600,58081,
58564,59049,59319,59536,60025,60516,61009,61504,62001,62500,
63001,63504,64000,64009,64516,65025,65536,66049,66564,67081,
67600,68121,68644,68921,69169,69696,70225,70756,71289,71824,
72361,72900,73441,73984,74088,74529,75076,75625,76176,76729,
77284,77841,78125,78400,78961,79507,79524,80089,80656,81225,
81796,82369,82944,83521,84100,84681,85184,85264,85849,86436,
87025,87616,88209,88804,89401,90000,90601,91125,91204,91809,
92416,93025,93636,94249,94864,95481,96100,96721,97336,97344,
97969,98596,99225,99856,100000,100489,101124,101761,102400,
103041,103684,103823,104329,104976,105625,106276,106929,
107584,108241,108900,109561,110224,110592,110889,111556,
112225,112896,113569,114244,114921,115600,116281,116964,
117649,118336,119025,119716,120409,121104,121801,122500,
123201,123904,124609,125000,125316,126025,126736,127449,
128164,128881,129600,130321,131044,131072,131769,132496,
132651,133225,133956,134689,135424,136161,136900,137641,
138384,139129,139876,140608,140625,141376,142129,142884,
143641,144400,145161,145924,146689,147456,148225,148877,
148996,149769,150544,151321,152100,152881,153664,154449,
155236,156025,156816,157464,157609,158404,159201,160000,
160801,161051,161604,162409,163216,164025,164836,165649,
166375,166464,167281,168100,168921,169744,170569,171396,
172225,173056,173889,174724,175561,175616,176400,177147,
177241,178084,178929,179776,180625,181476,182329,183184,
184041,184900,185193,185761,186624,187489,188356,189225,
190096,190969,191844,192721,193600,194481,195112,195364,
196249,197136,198025,198916,199809,200704,201601,202500,
203401,204304,205209,205379,206116,207025,207936,208849,
209764,210681,211600,212521,213444,214369,215296,216000,
216225,217156,218089,219024,219961,220900,221841,222784,
223729,224676,225625,226576,226981,227529,228484,229441,
230400,231361,232324,233289,234256,235225,236196,237169,
238144,238328,239121,240100,241081,242064,243049,244036,
245025,246016,247009,248004,248832,249001,250000,250047,
251001,252004,253009,254016,255025,256036,257049,258064,
259081,260100,261121,262144,263169,264196,265225,266256,
267289,268324,269361,270400,271441,272484,273529,274576,
274625,275625,276676,277729,278784,279841,279936,280900,
281961,283024,284089,285156,286225,287296,287496,288369,
289444,290521,291600,292681,293764,294849,295936,297025,
298116,299209,300304,300763,301401,302500,303601,304704,
305809,306916,308025,309136,310249,311364,312481,313600,
314432,314721,315844,316969,318096,319225,320356,321489,
322624,323761,324900,326041,327184,328329,328509,329476,
330625,331776,332929,334084,335241,336400,337561,338724,
339889,341056,342225,343000,343396,344569,345744,346921,
348100,349281,350464,351649,352836,354025,355216,356409,
357604,357911,358801,360000,361201,362404,363609,364816,
366025,367236,368449,369664,370881,371293,372100,373248,
373321,374544,375769,376996,378225,379456,380689,381924,
383161,384400,385641,386884,388129,389017,389376,390625,
391876,393129,394384,395641,396900,398161,399424,400689,
401956,403225,404496,405224,405769,407044,408321,409600,
410881,412164,413449,414736,416025,417316,418609,419904,
421201,421875,422500,423801,425104,426409,427716,429025,
430336,431649,432964,434281,435600,436921,438244,438976,
439569,440896,442225,443556,444889,446224,447561,448900,
450241,451584,452929,454276,455625,456533,456976,458329,
459684,461041,462400,463761,465124,466489,467856,469225,
470596,471969,473344,474552,474721,476100,477481,478864,
480249,481636,483025,484416,485809,487204,488601,490000,
491401,492804,493039,494209,495616,497025,498436,499849,
501264,502681,504100,505521,506944,508369,509796,511225,
512000,512656,514089,515524,516961,518400,519841,521284,
522729,524176,524288,525625,527076,528529,529984,531441,
532900,534361,535824,537289,537824,538756,540225,541696,
543169,544644,546121,547600,549081,550564,551368,552049,
553536,555025,556516,558009,559504,561001,562500,564001,
565504,567009,568516,570025,571536,571787,573049,574564,
576081,577600,579121,580644,582169,583696,585225,586756,
588289,589824,591361,592704,592900,594441,595984,597529,
599076,600625,602176,603729,605284,606841,608400,609961,
611524,613089,614125,614656,616225,617796,619369,620944,
622521,624100,625681,627264,628849,630436,632025,633616,
635209,636056,636804,638401,640000,641601,643204,644809,
646416,648025,649636,651249,652864,654481,656100,657721,
658503,659344,660969,662596,664225,665856,667489,669124,
670761,672400,674041,675684,677329,678976,680625,681472,
682276,683929,685584,687241,688900,690561,692224,693889,
695556,697225,698896,700569,702244,703921,704969,705600,
707281,708964,710649,712336,714025,715716,717409,719104,
720801,722500,724201,725904,727609,729000,729316,731025,
732736,734449,736164,737881,739600,741321,743044,744769,
746496,748225,749956,751689,753424,753571,755161,756900,
758641,759375,760384,762129,763876,765625,767376,769129,
770884,772641,774400,776161,777924,778688,779689,781456,
783225,784996,786769,788544,790321,792100,793881,795664,
797449,799236,801025,802816,804357,804609,806404,808201,
810000,811801,813604,815409,817216,819025,820836,822649,
823543,824464,826281,828100,829921,830584,831744,833569,
835396,837225,839056,840889,842724,844561,846400,848241,
850084,851929,853776,855625,857375,857476,859329,861184,
863041,864900,866761,868624,870489,872356,874225,876096,
877969,879844,881721,883600,884736,885481,887364,889249,
891136,893025,894916,896809,898704,900601,902500,904401,
906304,908209,910116,912025,912673,913936,915849,917764,
919681,921600,923521,925444,927369,929296,931225,933156,
935089,937024,938961,940900,941192,942841,944784,946729,
948676,950625,952576,954529,956484,958441,960400,962361,
964324,966289,968256,970225,970299,972196,974169,976144,
978121,980100,982081,984064,986049,988036,990025,992016,
994009,996004,998001,1000000
```

I'll use this data to make some plots.

*Last edited by krassi_holmz (2006-05-20 21:10:48)*

IPBLE: Increasing Performance By Lowering Expectations.

Offline

**krassi_holmz****Real Member**- Registered: 2005-12-02
- Posts: 1,905

Very interesting.

Look at the plot:

*Last edited by krassi_holmz (2006-05-20 21:13:39)*

IPBLE: Increasing Performance By Lowering Expectations.

Offline

**krassi_holmz****Real Member**- Registered: 2005-12-02
- Posts: 1,905

Here's a plot up to 1000:

*Last edited by krassi_holmz (2006-05-20 21:15:21)*

IPBLE: Increasing Performance By Lowering Expectations.

Offline

**krassi_holmz****Real Member**- Registered: 2005-12-02
- Posts: 1,905

It looks familiar.

IPBLE: Increasing Performance By Lowering Expectations.

Offline

**krassi_holmz****Real Member**- Registered: 2005-12-02
- Posts: 1,905

Look:

(sorry but I hurry and can't make better for now)

IPBLE: Increasing Performance By Lowering Expectations.

Offline

**krassi_holmz****Real Member**- Registered: 2005-12-02
- Posts: 1,905

Now some pure maths:

1. (it is simple):

2. find the nmber of all perfect powers less or equal to x.

3. What can you say about the increasing of P?

I think it diverges.(the increasing, not the function, although F diverges too).

*Last edited by krassi_holmz (2006-05-20 21:36:17)*

IPBLE: Increasing Performance By Lowering Expectations.

Offline

**krassi_holmz****Real Member**- Registered: 2005-12-02
- Posts: 1,905

Let

means

, where p_i is the n=th prime.

IPBLE: Increasing Performance By Lowering Expectations.

Offline

**krassi_holmz****Real Member**- Registered: 2005-12-02
- Posts: 1,905

Now, if

(1).

p divides i with probability 1/p, so the probability that (1) is tue, is 1/p^n.

So the probability x to be a perfect power is:

, where P is the set of prime numbers.

But now, every i may be every number between 0 and infty and the resulting x will be always different, so if is the set of all numbers that are divisible only by , then exactly of them will be perfect powers.

Now, when n goes to infty, we get that the distribution of the perfect powers is in the set of the integers is:

.

Now that's a hard sum!!!

(it will be < 1, because )

*Last edited by krassi_holmz (2006-05-20 22:16:25)*

IPBLE: Increasing Performance By Lowering Expectations.

Offline

**krassi_holmz****Real Member**- Registered: 2005-12-02
- Posts: 1,905

Now, how to find

???

Any ideas?

(and you can disscuss my work and report for errors)

IPBLE: Increasing Performance By Lowering Expectations.

Offline

**mikau****Member**- Registered: 2005-08-22
- Posts: 1,504

I see I'm not the only one who has conversations with himself.

I like this function, and the graph is cool. Looks like a nice parabolla to me. However I believe this function is not continuous or differentiable. Still I like nifty functions like this.

A logarithm is just a misspelled algorithm.

Offline

**luca-deltodesco****Member**- Registered: 2006-05-05
- Posts: 1,470

mikau wrote:

I see I'm not the only one who has conversations with himself.

i only usually do when im figuring something out and asking at the same time, and then end up answering myself before anyone responds

The Beginning Of All Things To End.

The End Of All Things To Come.

Offline

**Ricky****Moderator**- Registered: 2005-12-04
- Posts: 3,791

However I believe this function is not continuous or differentiable.

No function defined on the integers (or naturals as is this case) can be continuous or differentiable. For any function to be continuous at any given point, that point must be a limit point. In functions of integers, there are no limit points.

Edit:

Actually, it's a bit more complicated than that. For example, the function:

f(n) = 1/n for all n in N

Is continous at 0 (when n goes to infinity). But the function krassi is talking about has no limit points.

Very cool function krassi.

"In the real world, this would be a problem. But in mathematics, we can just define a place where this problem doesn't exist. So we'll go ahead and do that now..."

Offline

**mikau****Member**- Registered: 2005-08-22
- Posts: 1,504

No function defined on the integers (or naturals as is this case) can be continuous or differentiable.

Right, I know that, I just wasn't sure if krassi had developed a formula for the intermediate points.

A logarithm is just a misspelled algorithm.

Offline

**Mathaphobe****Member**- Registered: 2006-05-20
- Posts: 18

-To tell the truth i think we all talk to our selves.. (after 3 or 4 Dr. Peppers i know i do...)

-As for the grapic thingy that is way beyond my abiliy so It looks cool...

-Though i'd just use a graphic calculator there are no errors in those at least i hope not...

Do you like my new avatar? (even if you don't i do )

(it's victor from oh my gods)

-An Incremental Development

Offline

**John E. Franklin****Member**- Registered: 2005-08-29
- Posts: 3,588

kras, why no 'L' in this line?: const long int n=1000000**L**;

**igloo** **myrtilles** **fourmis**

Offline

**Ricky****Moderator**- Registered: 2005-12-04
- Posts: 3,791

In most compilers, long is the same as int, 32 bits. So it wouldn't matter. Long is (right now) an artifact of when you had 16 bit ints and 32 bit longs. But now ints are 32 bits, and having a 64 bit int would make a heck of a lot of more work for the processor, it's really not needed. Although compilers normally also have 64 bit ints like microsoft's INT_64.

But even if it did, ints are 32 bits. That can hold up to 2,147,483,648 values when signed. Thus, 1,000,000 can be stored in 32 bits, so there is no worry anyways.

Now what is going on there is an implicit conversion. The compiler sees that line, and rewrites it as:

const long int n = (const long int)1000000;

You don't have to do the conversion as the compiler will do it for you. Many programmers see this as bad practice though. I think that as *long* as you know what's going on, it's fine to do.

"In the real world, this would be a problem. But in mathematics, we can just define a place where this problem doesn't exist. So we'll go ahead and do that now..."

Offline

**George,Y****Member**- Registered: 2006-03-12
- Posts: 1,316

Since p is a prime number, how can it divide i?

*Last edited by George,Y (2006-05-22 23:15:48)*

**X'(y-Xβ)=0**

Offline

**krassi_holmz****Real Member**- Registered: 2005-12-02
- Posts: 1,905

Ricky wrote:

In most compilers, long is the same as int, 32 bits. So it wouldn't matter. Long is (right now) an artifact of when you had 16 bit ints and 32 bit longs. But now ints are 32 bits, and having a 64 bit int would make a heck of a lot of more work for the processor, it's really not needed. Although compilers normally also have 64 bit ints like microsoft's INT_64.

But even if it did, ints are 32 bits. That can hold up to 2,147,483,648 values when signed. Thus, 1,000,000 can be stored in 32 bits, so there is no worry anyways.

Now what is going on there is an implicit conversion. The compiler sees that line, and rewrites it as:

const long int n = (const long int)1000000;

You don't have to do the conversion as the compiler will do it for you. Many programmers see this as bad practice though. I think that as

longas you know what's going on, it's fine to do.

ok. 32bit integers.

but why i get error when n is 2 millions

please.

IPBLE: Increasing Performance By Lowering Expectations.

Offline

**krassi_holmz****Real Member**- Registered: 2005-12-02
- Posts: 1,905

3 is a prime.

3 divides 6 for example

IPBLE: Increasing Performance By Lowering Expectations.

Offline

**John E. Franklin****Member**- Registered: 2005-08-29
- Posts: 3,588

kras, the biggest number I got to work for n is:

const long int nq=1028428L; //1000000;

The next integer larger creates a beep on running.

I changed the single letter variables to two letter variables just in case there was a conflict.

**igloo** **myrtilles** **fourmis**

Offline

**krassi_holmz****Real Member**- Registered: 2005-12-02
- Posts: 1,905

Yes. But why?

IPBLE: Increasing Performance By Lowering Expectations.

Offline

**John E. Franklin****Member**- Registered: 2005-08-29
- Posts: 3,588

kras, I recompiled with a different C compiler, and now it Kraps out on this number:

//lower 1035585

const long int nq=1035584L; //1000000;

//higher 1035584

And by the way, the highest power number I found was 1034289 and a nice mirror image one is 1030301.

*Last edited by John E. Franklin (2006-05-23 03:21:31)*

**igloo** **myrtilles** **fourmis**

Offline

**John E. Franklin****Member**- Registered: 2005-08-29
- Posts: 3,588

We have to do something about this foul word changer.

It won't even allow C-r-a-pped out, which means stopped working.

**igloo** **myrtilles** **fourmis**

Offline