mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Blogorrhea > MattcAnderson

Reply
 
Thread Tools
Old 2022-06-23, 20:03   #1
MattcAnderson
 
MattcAnderson's Avatar
 
"Matthew Anderson"
Dec 2010
Oregon, USA

3·389 Posts
Smile 10^a+1 is prime at least twice

Hi again everybody,
I'm curiouse about positibe integers of the form 10^a + 1 where a is a
positive integer.

see my code.

> print("prime factorization of numbers of the form 10^a + 1");
for a to 20 do
b := 10^a+1;
c := ifactor(10^a+1);
print(b, " factors as ", c)
end do;
<begin Maple output>
"prime factorization of numbers of the form 10^a + 1"
11, " factors as ", (11)
101, " factors as ", (101)

<note 11 and 101 are prime numbers> </note>
<Maple output>
1001, " factors as ", (7) (11) (13)
10001, " factors as ", (73) (137)
100001, " factors as ", (11) (9091)
1000001, " factors as ", (101) (9901)
10000001, " factors as ", (11) (909091)
100000001, " factors as ", (17) (5882353)
1000000001, " factors as ", (7) (11) (13) (19) (52579) <one billion>
</Maple output>
<joke> Now that you know that One Billion has prime factorization of
7*11*13*19*52579, your life is complete. <smile> </joke>

<note> Another calculation shows that.
10^a + 1 is a composite number for integers 3<a<86.

The pattern seems to suggest that 10^a + 1 is always composite for integers a>3.
But a pattern does not make a theorem.
Anyone care to take the calculation furthur?

Regards,
Matt

PS Has someone else already done this calculation? Can we look this up somewhere?
Cheers,
Matt


P.S. After nearly a 5 hour calculation, and I trust my computer for
accurate results, I can say with certainty that the positive integers
of the form

10^a+1 are composite for integers 'a' with 3 <= a <= 97.

This I am sure of.

I'm sure someone else could extend the dataset.

Regards,
Matthew Charles Anderson

PPS Here is my raw Maple code

> restart*print("prime factorization of numbers of the form 10^a + 1");
for a to 1000 do
b := 10^a+1;
c := ifactor(10^a+1);
if isprime(b) then print(b, " factors as ", c) end if
end do;
<Maple outuput>
"prime factorization of numbers of the form 10^a + 1"
restart ()
11, " factors as ", (11)
101, " factors as ", (101)
Warning, computation interrupted
<check to see how far it calculated in 4.7 hours>(a checkpoint)
a
97

#interesting_mathematical_trivia

So to reiterate,
11 is prime, 101 is prime, and 10^a + 1 is not prime for a= 3,4,5,...,97.

Have a nice day.
MattcAnderson is offline   Reply With Quote
Old 2022-06-23, 20:34   #2
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

22×1,063 Posts
Default

10^2^k+1 is a Generalized Fermat Number. There are very few Fermat Numbers that are prime. There will be fewer base 10 GFN primes is my guess.

Last fiddled with by paulunderwood on 2022-06-23 at 20:47
paulunderwood is offline   Reply With Quote
Old 2022-06-23, 20:49   #3
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

3·1,117 Posts
Default

All odd a>=3 is divisible by 11: a=2n+1
102n+1 + 1 = 100n * 10 + 1 = 1n * 10 + 1 = 0 (mod 11)

All a=4n+2 >=6 is divisible by 101:
104n+2 + 1 = 10000n * 100 + 1 = 1n * 100 + 1 = 0 (mod 101)

All a=8n+4 >=4 is divisible by 73:
108n+4 + 1 =100000000n * 10000 + 1 = 1n * 10000 + 1 = 0 (mod 73)

There are probably several more of these.

Last fiddled with by ATH on 2022-06-23 at 20:51
ATH is offline   Reply With Quote
Old 2022-06-23, 21:03   #4
kar_bon
 
kar_bon's Avatar
 
Mar 2006
Germany

1011100101112 Posts
Default

5 hours of energy which could be saved by searching a well known database of such formats of number, see Studio Kamada for factors of 10^n+1 for n=1 to 150,000.

FactorDB also contains those factorizations already.
kar_bon is offline   Reply With Quote
Old 2022-06-23, 21:52   #5
charybdis
 
charybdis's Avatar
 
Apr 2020

19×43 Posts
Default

If k is odd, then x^k+1 factorizes as (x+1)(x^(k-1)-x^(k-2)+...-x+1). Substituting 10^m for x, we see that 10^km+1 is divisible by 10^m+1 if k is odd. In other words, 10^n+1 cannot be prime if n has an odd factor greater than 1.
The only values of n for which this is not the case are powers of 2, so these are the only exponents for which it is possible for 10^n+1 to be prime. They are Generalized Fermat numbers as Paul says.

See Wilfrid Keller's page for the status of the base 10 GFNs. No primes are known apart from 11, and it is almost certain that no more exist. 10^(2^31)+1 is the smallest with unknown status.
charybdis is offline   Reply With Quote
Old 2022-06-24, 00:45   #6
MattcAnderson
 
MattcAnderson's Avatar
 
"Matthew Anderson"
Dec 2010
Oregon, USA

3·389 Posts
Smile

Thank you for all the insightful replies.
Learning is an ongoing process.

I try to summarize

I never fully understood the term Generalized Fermat Number, until now.

I will accept the definition

a^(2^k) + 1 is defined as a Generalized Fermat Number

10^(2^k) + 1 as a Generalized Fermat Number with a=10.
see mathworld.Wolfram.com reference
https://mathworld.wolfram.com/GeneralizedFermatNumber.html



Here are some (somewhat new to me) identities that are related.

x^3 + 1 = (x+1)*(x^2 - x + 1).

x^5 + 1 = (x+1)*(x^4 - x^3 + x^2 - x + 1).

similarly with x^7 + 1 and bigger odd exponents.

If we let x=10, then we have cases when divisibility by 11 happens.

for example, as I was shown
10^3+1 = 11*91
10^5+1 = 11*9091
10^7+1 = 11*909091
10^9+1 = 11*90909091

there is a (somewhat more clear now) pattern here.
Let's call it an exercise in learning, or an exploration.

Time for a YouTube.com song
See "The Best of Johnny Nash"
https://www.youtube.com/watch?v=g_rB4v75jqU


On a personal note,
Okay, I do not have my textbooks any more, because
I have communal living. Over the years, some of my things have been stolen.
All my remaining textbooks are in my back shed,
and that is my space, only my wife has partially filled it with
toilet paper and supplies. I will find a way to continue my academic journey.

and have fun... and love life.
Matt
PS No matter what happens, it is worth it.

Here is the second part.

This is some very good learning for me.
To call out the helpful replies one by one,

ATH, you make some good points,
There are several general cases when we have divisibility by 11, 101, and 73.

These patterns are often difficult to flesh out, if you don't know about them.

'nearly hidden gems' if you will.

I looked at Studio Kamada and downloaded some of the data
also, the positive integer factorizations are worked out, and presented clearly.


Surely, I am not the first person who has considered numbers of this type.
(to be specific 10^a + 1 = S) where S is for Special number.

I looked at
https://stdkmd.net/ (Studio Kamada)
Specifically
stdkmd.net/nrr/
Then scroll to section 9.1 and look at second link
specifically
https://stdkmd.net/nrr/repunit/10001.htm
requires some scrolling
okay too many links

In this exploration, I did not need to 're-invent the wheel' but
to 'look up a reference'.

I feel enlightened about this number theory now.
However, tomorrow I will be onto other things.

Last fiddled with by MattcAnderson on 2022-06-24 at 01:04 Reason: a second block of text copied from notepad #grateful now grammer errors
MattcAnderson is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Can a (decimal) repunit prime (other than 11) be a member of twin prime pair? sweety439 And now for something completely different 22 2022-03-23 00:22
Prime residues of near-prime modulo a prime robert44444uk Math 27 2021-11-21 11:00
How to get to a prime from the previous prime number (sieve of Eratosthenes rediscovered) AddieJ Miscellaneous Math 15 2021-05-11 14:57
Congruent prime numbers that preserves the modulo as the largest prime factor of the sum Hugo1177 Miscellaneous Math 5 2021-02-11 07:40
Primes of the form prime(a)+prime(b)+1=prime(c) and prime(b)-prime(a)-1=prime (c) Hugo1177 Miscellaneous Math 1 2021-01-05 08:09

All times are UTC. The time now is 15:39.


Wed Aug 17 15:39:47 UTC 2022 up 41 days, 10:27, 1 user, load averages: 1.45, 1.26, 1.20

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔