[QUOTE=3.14159;240816]Counterexample: 11632 * 176[sup]176[/sup] + 1 is prime. Neither 176 nor 11632 is a multiple of three.[/QUOTE]

what I listed off was for 6n+1 for a +1 side number your "counterexample" is 6n+5.

[QUOTE=3.14159;240825]7000-digit numbers? O rly?[/QUOTE]

[CODE]> sum(n=10^7000,10^7000+10^3,fac(n))
time = 3,740 ms.
%1 = 475[/CODE]

fac() is my simple code to test for prime factors between 1070 and 10^6. Running it several times gave me times as bad as 3.75 milliseconds per iteration and as good as 3.72 milliseconds per iteration. Oops, fencepost error -- I actually have 1001 numbers, so that decreases my average time by an insignificant amount.

Edit: And of course these are 7001-digit numbers; 7000-digit numbers would be slightly (insignificantly) faster.

[QUOTE=CRGreathouse;240840][CODE]> sum(n=10^7000,10^7000+10^3,fac(n))
time = 3,740 ms.
%1 = 475[/CODE]

fac() is my simple code to test for prime factors between 1070 and 10^6. Running it several times gave me times as bad as 3.75 milliseconds per iteration and as good as 3.72 milliseconds per iteration. Oops, fencepost error -- I actually have 1001 numbers, so that decreases my average time by an insignificant amount.

Edit: And of course these are 7001-digit numbers; 7000-digit numbers would be slightly (insignificantly) faster.[/QUOTE]

But you did not select a number that was divisible by primes from 2 to 1069.

[QUOTE=3.14159;240857]But you did not select a number that was divisible by primes from 2 to 1069.[/QUOTE]

[QUOTE=CRGreathouse;240840]fac() is my simple code [B]to test for prime factors between 1070 and 10^6[/B]. [/QUOTE]

He compensated for that.

[QUOTE=kar_bon;240795]I don't know, how you search for such primes of the form k*b^b+/-1.
[/QUOTE]

for 6n+1 form k*b^b must divide 6 ( which can come from either one being divisible by 6 or a combination of 2 and 3)

6n+5 means that for +1 side k*b^b must be 6n+4 ( combos of 2 and 3n+2 seem likely)

for the -1 side the first part is accurate to get 6n+5

as for 6n+1 ( k*b^b must be 6n+4 which looks to be the reverse)


so does this narrow things down ?

[CODE](12:09)>for(k=1,20,for(b=1,100,if((k*b^b)%6==0 || (k*b^b)%6==4,print1(k","b":"))))
1,2:1,4:1,6:1,8:1,10:1,12:1,14:1,16:1,18:1,20:1,22:1,24:1,26:1,28:1,30:1,32:1,34:1,36:1,38:1,40:1,42:1,44:1,46:1,48:1,50:1,52:1,54:1,56:1,58:1,60:1,62:1,64:1,66:1,68:1,70:1,72:1,74:1,76:1,78:1,80:1,82:1,84:1,86:1,88:1,90:1,92:1,94:1,96:1,98:1,100:2,3:2,5:2,6:2,9:2,11:2,12:2,15:2,17:2,18:2,21:2,23:2,24:2,27:2,29:2,30:2,33:2,35:2,36:2,39:2,41:2,42:2,45:2,47:2,48:2,51:2,53:2,54:2,57:2,59:2,60:2,63:2,65:2,66:2,69:2,71:2,72:2,75:2,77:2,78:2,81:2,83:2,84:2,87:2,89:2,90:2,93:2,95:2,96:2,99:3,2:3,4:3,6:3,8:3,10:3,12:3,14:3,16:3,18:3,20:3,22:3,24:3,26:3,28:3,30:3,32:3,34:3,36:3,38:3,40:3,42:3,44:3,46:3,48:3,50:3,52:3,54:3,56:3,58:3,60:3,62:3,64:3,66:3,68:3,70:3,72:3,74:3,76:3,78:3,80:3,82:3,84:3,86:3,88:3,90:3,92:3,94:3,96:3,98:3,100:4,1:4,2:4,3:4,4:4,6:4,7:4,8:4,9:4,10:4,12:4,13:4,14:4,15:4,16:4,18:4,19:4,20:4,21:4,22:4,24:4,25:4,26:4,27:4,28:4,30:4,31:4,32:4,33:4,34:4,36:4,37:4,38:4,39:4,40:4,42:4,43:4,44:4,45:4,46:4,48:4,49:4,50:4,51:4,52:4,54:4,55:4,56:4,57:4,58:4,60:4,61:4,62:4,63:4,64:4,66:4,67:4,68:4,69:4,70:4,72:4,73:4,74:4,75:4,76:4,78:4,79:4,80:4,81:4,82:4,84:4,85:4,86:4,87:4,88:4,90:4,91:4,92:4,93:4,94:4,96:4,97:4,98:4,99:4,100:5,6:5,12:5,18:5,24:5,30:5,36:5,42:5,48:5,54:5,60:5,66:5,72:5,78:5,84:5,90:5,96:6,1:6,2:6,3:6,4:6,5:6,6:6,7:6,8:6,9:6,10:6,11:6,12:6,13:6,14:6,15:6,16:6,17:6,18:6,19:6,20:6,21:6,22:6,23:6,24:6,25:6,26:6,27:6,28:6,29:6,30:6,31:6,32:6,33:6,34:6,35:6,36:6,37:6,38:6,39:6,40:6,41:6,42:6,43:6,44:6,45:6,46:6,47:6,48:6,49:6,50:6,51:6,52:6,53:6,54:6,55:6,56:6,57:6,58:6,59:6,60:6,61:6,62:6,63:6,64:6,65:6,66:6,67:6,68:6,69:6,70:6,71:6,72:6,73:6,74:6,75:6,76:6,77:6,78:6,79:6,80:6,81:6,82:6,83:6,84:6,85:6,86:6,87:6,88:6,89:6,90:6,91:6,92:6,93:6,94:6,95:6,96:6,97:6,98:6,99:6,100:7,2:7,4:7,6:7,8:7,10:7,12:7,14:7,16:7,18:7,20:7,22:7,24:7,26:7,28:7,30:7,32:7,34:7,36:7,38:7,40:7,42:7,44:7,46:7,48:7,50:7,52:7,54:7,56:7,58:7,60:7,62:7,64:7,66:7,68:7,70:7,72:7,74:7,76:7,78:7,80:7,82:7,84:7,86:7,88:7,90:7,92:7,94:7,96:7,98:7,100:8,3:8,5:8,6:8,9:8,11:8,12:8,15:8,17:8,18:8,21:8,23:8,24:8,27:8,29:8,30:8,33:8,35:8,36:8,39:8,41:8,42:8,45:8,47:8,48:8,51:8,53:8,54:8,57:8,59:8,60:8,63:8,65:8,66:8,69:8,71:8,72:8,75:8,77:8,78:8,81:8,83:8,84:8,87:8,89:8,90:8,93:8,95:8,96:8,99:9,2:9,4:9,6:9,8:9,10:9,12:9,14:9,16:9,18:9,20:9,22:9,24:9,26:9,28:9,30:9,32:9,34:9,36:9,38:9,40:9,42:9,44:9,46:9,48:9,50:9,52:9,54:9,56:9,58:9,60:9,62:9,64:9,66:9,68:9,70:9,72:9,74:9,76:9,78:9,80:9,82:9,84:9,86:9,88:9,90:9,92:9,94:9,96:9,98:9,100:10,1:10,2:10,3:10,4:10,6:10,7:10,8:10,9:10,10:10,12:10,13:10,14:10,15:10,16:10,18:10,19:10,20:10,21:10,22:10,24:10,25:10,26:10,27:10,28:10,30:10,31:10,32:10,33:10,34:10,36:10,37:10,38:10,39:10,40:10,42:10,43:10,44:10,45:10,46:10,48:10,49:10,50:10,51:10,52:10,54:10,55:10,56:10,57:10,58:10,60:10,61:10,62:10,63:10,64:10,66:10,67:10,68:10,69:10,70:10,72:10,73:10,74:10,75:10,76:10,78:10,79:10,80:10,81:10,82:10,84:10,85:10,86:10,87:10,88:10,90:10,91:10,92:10,93:10,94:10,96:10,97:10,98:10,99:10,100:11,6:11,12:11,18:11,24:11,30:11,36:11,42:11,48:11,54:11,60:11,66:11,72:11,78:11,84:11,90:11,96:12,1:12,2:12,3:12,4:12,5:12,6:12,7:12,8:12,9:12,10:12,11:12,12:12,13:12,14:12,15:12,16:12,17:12,18:12,19:12,20:12,21:12,22:12,23:12,24:12,25:12,26:12,27:12,28:12,29:12,30:12,31:12,32:12,33:12,34:12,35:12,36:12,37:12,38:12,39:12,40:12,41:12,42:12,43:12,44:12,45:12,46:12,47:12,48:12,49:12,50:12,51:12,52:12,53:12,54:12,55:12,56:12,57:12,58:12,59:12,60:12,61:12,62:12,63:12,64:12,65:12,66:12,67:12,68:12,69:12,70:12,71:12,72:12,73:12,74:12,75:12,76:12,77:12,78:12,79:12,80:12,81:12,82:12,83:12,84:12,85:12,86:12,87:12,88:12,89:12,90:12,91:12,92:12,93:12,94:12,95:12,96:12,97:12,98:12,99:12,100:13,2:13,4:13,6:13,8:13,10:13,12:13,14:13,16:13,18:13,20:13,22:13,24:13,26:13,28:13,30:13,32:13,34:13,36:13,38:13,40:13,42:13,44:13,46:13,48:13,50:13,52:13,54:13,56:13,58:13,60:13,62:13,64:13,66:13,68:13,70:13,72:13,74:13,76:13,78:13,80:13,82:13,84:13,86:13,88:13,90:13,92:13,94:13,96:13,98:13,100:14,3:14,5:14,6:14,9:14,11:14,12:14,15:14,17:14,18:14,21:14,23:14,24:14,27:14,29:14,30:14,33:14,35:14,36:14,39:14,41:14,42:14,45:14,47:14,48:14,51:14,53:14,54:14,57:14,59:14,60:14,63:14,65:14,66:14,69:14,71:14,72:14,75:14,77:14,78:14,81:14,83:14,84:14,87:14,89:14,90:14,93:14,95:14,96:14,99:15,2:15,4:15,6:15,8:15,10:15,12:15,14:15,16:15,18:15,20:15,22:15,24:15,26:15,28:15,30:15,32:15,34:15,36:15,38:15,40:15,42:15,44:15,46:15,48:15,50:15,52:15,54:15,56:15,58:15,60:15,62:15,64:15,66:15,68:15,70:15,72:15,74:15,76:15,78:15,80:15,82:15,84:15,86:15,88:15,90:15,92:15,94:15,96:15,98:15,100:16,1:16,2:16,3:16,4:16,6:16,7:16,8:16,9:16,10:16,12:16,13:16,14:16,15:16,16:16,18:16,19:16,20:16,21:16,22:16,24:16,25:16,26:16,27:16,28:16,30:16,31:16,32:16,33:16,34:16,36:16,37:16,38:16,39:16,40:16,42:16,43:16,44:16,45:16,46:16,48:16,49:16,50:16,51:16,52:16,54:16,55:16,56:16,57:16,58:16,60:16,61:16,62:16,63:16,64:16,66:16,67:16,68:16,69:16,70:16,72:16,73:16,74:16,75:16,76:16,78:16,79:16,80:16,81:16,82:16,84:16,85:16,86:16,87:16,88:16,90:16,91:16,92:16,93:16,94:16,96:16,97:16,98:16,99:16,100:17,6:17,12:17,18:17,24:17,30:17,36:17,42:17,48:17,54:17,60:17,66:17,72:17,78:17,84:17,90:17,96:18,1:18,2:18,3:18,4:18,5:18,6:18,7:18,8:18,9:18,10:18,11:18,12:18,13:18,14:18,15:18,16:18,17:18,18:18,19:18,20:18,21:18,22:18,23:18,24:18,25:18,26:18,27:18,28:18,29:18,30:18,31:18,32:18,33:18,34:18,35:18,36:18,37:18,38:18,39:18,40:18,41:18,42:18,43:18,44:18,45:18,46:18,47:18,48:18,49:18,50:18,51:18,52:18,53:18,54:18,55:18,56:18,57:18,58:18,59:18,60:18,61:18,62:18,63:18,64:18,65:18,66:18,67:18,68:18,69:18,70:18,71:18,72:18,73:18,74:18,75:18,76:18,77:18,78:18,79:18,80:18,81:18,82:18,83:18,84:18,85:18,86:18,87:18,88:18,89:18,90:18,91:18,92:18,93:18,94:18,95:18,96:18,97:18,98:18,99:18,100:19,2:19,4:19,6:19,8:19,10:19,12:19,14:19,16:19,18:19,20:19,22:19,24:19,26:19,28:19,30:19,32:19,34:19,36:19,38:19,40:19,42:19,44:19,46:19,48:19,50:19,52:19,54:19,56:19,58:19,60:19,62:19,64:19,66:19,68:19,70:19,72:19,74:19,76:19,78:19,80:19,82:19,84:19,86:19,88:19,90:19,92:19,94:19,96:19,98:19,100:20,3:20,5:20,6:20,9:20,11:20,12:20,15:20,17:20,18:20,21:20,23:20,24:20,27:20,29:20,30:20,33:20,35:20,36:20,39:20,41:20,42:20,45:20,47:20,48:20,51:20,53:20,54:20,57:20,59:20,60:20,63:20,65:20,66:20,69:20,71:20,72:20,75:20,77:20,78:20,81:20,83:20,84:20,87:20,89:20,90:20,93:20,95:20,96:20,99:[/CODE]

This is what I get for k= 1 to 20 ; and b= 1 to 100 this any help ?

[QUOTE=science_man_88;240958]This is what I get for k= 1 to 20 ; and b= 1 to 100 this any help ?[/QUOTE]

I can't imagine.

But let's talk about Pari issues here. For a moment, I'll change your code to count the occurrences rather than print them:
[CODE]sum(k=1,20,sum(b=1,100,(k*b^b)%6==0 || (k*b^b)%6==4))[/CODE]
This runs pretty quickly, so let's scale the b-range up to 1000:
[CODE]sum(k=1,20,sum(b=1,1000,(k*b^b)%6==0 || (k*b^b)%6==4))[/CODE]
This takes 1.31 seconds on a somewhat slow machine. Converting to Mod:
[CODE]sum(k=1,20,sum(b=1,1000,Mod(k*b^b,6)==0 || Mod(k*b^b,6)==4))[/CODE]
doesn't save time, since we calculate the full-sized integer and send it to the Mod function. But we can do calculations with the Mod object, like so:
[CODE]sum(k=1,20,sum(b=1,1000,k*Mod(b^b,6)==0 || k*Mod(b^b,6)==4))[/CODE]
This isn't faster either, though, since the big part (b^b) is still calculated in full form. 1000^1000 has 3001 decimal digits, right? We don't need to keep all of that if we're just going to look at the last (base-6) digit, so let's move the exponent out of the Mod. This way we're doing *modular* exponentiation rather than integer exponentiation, and so we're letting Pari reduce to smaller numbers in the middle of the calculation:
[CODE]sum(k=1,20,sum(b=1,1000,k*Mod(b,6)^b==0 || k*Mod(b,6)^b==4))[/CODE]
This gives the same answer as the others but runs ten times faster. What's more, it scales vastly better: instead of the 11 minutes that the original version would have taken to calculate b up to 10,000, this one takes less than a second.

[QUOTE=CRGreathouse;240993][CODE]sum(k=1,20,sum(b=1,1000,k*Mod(b,6)^b==0 || k*Mod(b,6)^b==4))[/CODE]
This gives the same answer as the others but runs ten times faster. What's more, it scales vastly better: instead of the 11 minutes that the original version would have taken to calculate b up to 10,000, this one takes less than a second.[/QUOTE]

Why takes
[code]
sum(k=1,20,sum(b=1,1000,x=k*Mod(b,6)^b;x==0 || x==4))
[/code]
longer than the above although the Mod is calculated only once?

[QUOTE=kar_bon;240999]Why takes
[code]
sum(k=1,20,sum(b=1,1000,x=k*Mod(b,6)^b;x==0 || x==4))
[/code]
longer than the above although the Mod is calculated only once?[/QUOTE]

They should take about the same amount of time (both 109 milliseconds on this machine). Small differences in time are unreliable in general.

Also, a small effect: As you move to more expensive calculations storing the results becomes a good strategy for saving time. When the calculations are cheap, sometimes allocating memory to store an object ends up taking more time than just calculating and discarding.

Doing it the _right_ way might be faster still:

[CODE]sum(k=1,20,sum(b=1,1000,k*Mod(b,2)^b!=-1 && k*Mod(b,3)^b!=-1))[/CODE]

which, upon a moment's thought, simplifies to:

[CODE]sum(k=1,20,sum(b=1,1000,(k*b)%2 == 0 && k*Mod(b,3)^b!=-1))[/CODE]

Continuing the tutorial:
There is significant duplication of effort here; in particular each modular exponentiation is done 20 times. Let's remove that by storing them. This will require changing the order of the loops:
[CODE]{sum(b=1,10000,
M=Mod(b,6)^b;
sum(k=1,20,k*M==0 || k*M==4)
)}[/CODE]
This only ends up saving about 15-20%; somewhat disappointing. Of course the savings would be more striking had I raised the k limit instead of the n limit.

We can still do better! There is a finite (and quite small in this case) set of values that the modulus can take on here. Similarly, we only care about the exponent mod 2 (except for small values, in this case 0). So you can actually tell which values will be printed by working mod lcm(6, 2) = 6. Once you work out each of these values, you can take that intmod and multiply it by the k:
[CODE]{blim=10000;
sum(i=1,6,
M=Mod(i,6)^i;
sum(k=1,20,k*M==0 || k*M==4)*(blim\6 + (blim%6 >= i))
)}[/CODE]
Now the code is fast even for a b-limit of 10^100, where simple enumeration would not be possible. Even if we wanted to enumerate, we could use a forstep with pre-calculated residues; this would be better than reducing large numbers repeatedly.