Finding a digit in a specific position

  • Thread starter WWGD
  • Start date
WWGD
Science Advisor
Gold Member
5,049
2,269

Summary:

We are given a number as a power. How to find the kth digit of a power.

Main Question or Discussion Point

Hi,
In another forum someone asked how to find the kth digit of a large prime given in the form ##2^t-1 ## , where t is a 6-digit (decimal) number. I was thinking maybe using some SQL string function , though I am not sure if input strings must be entered explicitly. Can anyone think of some other way?
 
Last edited by a moderator:

Answers and Replies

33,579
9,315
How would SQL calculate ##2^t##? If you have the number in decimal picking the k'th element is easy.

##2^t## in binary is trivial, so you just have to convert it to decimal. There are efficient algorithms for that.
 
pbuk
Gold Member
1,159
231
This is called a Mersenne Prime, and there are only 5 of them that satisfy the given condition with approximately 30,000 to 260,000 decimal digits.

Calculating such large integers is simple in any language with a Big Integer library, or you can download a text file from mersenne.org.

SQL is designed for a single purpose: extracting information from a relational database and would not be an appropriate choice.
 
WWGD
Science Advisor
Gold Member
5,049
2,269
This is called a Mersenne Prime, and there are only 5 of them that satisfy the given condition with approximately 30,000 to 260,000 decimal digits.

Calculating such large integers is simple in any language with a Big Integer library, or you can download a text file from mersenne.org.

SQL is designed for a single purpose: extracting information from a relational database and would not be an appropriate choice.
I agree in general but now SQL Server includes Python ( and an ML Server) and I though maybe these could be combined to make the process more effective. But , yes, apologies to all since my post was mostly speculative with no specifics. Edit: I should have said Sql Server instead ( of just Sql), which is no longer just about Sql but it has evolved into a full data platform, including capabilities for Python, R and machine-learning. It seems all this power may be used to do current computations more effective.
 
Last edited:
pbuk
Gold Member
1,159
231
I had time on my hands on the commute again... https://jsfiddle.net/pbinuk/y6mbt94x/.

Edit: requires a browser that supports BigInt (i.e. recent and not IE, Edge or Safari).
 
33,579
9,315
Why would you use SQL to call python if you can simply run python?
I don't see how SQL would do anything useful here.
 
WWGD
Science Advisor
Gold Member
5,049
2,269
Sorry, I likely fell for the temptations of big machinery at the expense of simplicity and common sense. It's like owning a Ferrari and just using it to go to the corner store. Curious to take it out on the bahn.
 
Baluncore
Science Advisor
7,059
2,218
In another forum someone asked how to find the kth digit of a large prime given in the form 2^t-1 , where t is a 6-digit (decimal) number.
Write t as a binary number. For 6 digits you will have about 20 bits, and 20 loops to perform later.
You need two decimal registers, each must hold at least k digits. Beyond k, the carry is irrelevant.

The first register starts at 1 and holds progressively larger powers of two. Each loop you double that register by simply adding it to itself.
The other register starts at 1, whenever a bit of t is set, the second register is multiplied by the powers register.
That requires only a k * k digit multiply.

When you have finished the set binary bits of t, subtract one.
Look at the k'th digit.
 

Related Threads for: Finding a digit in a specific position

Replies
10
Views
8K
  • Last Post
Replies
3
Views
3K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
12
Views
14K
  • Last Post
Replies
1
Views
5K
  • Last Post
Replies
3
Views
7K
  • Last Post
Replies
7
Views
4K
Top